Problem B
The Imp

You arrive in Ye Olde Magic Shoppe with some hard-earned gold to purchase wondrous and unique magic items. There are $n$ such items in the shop, each of them locked in a special magic box. The $i$-th box costs $c_ i$ gold pieces to buy, and contains an item worth $v_ i$ gold pieces. The costs and item values are known to you, as you have previously read, mastered, and memorized Ye Olde Magic Catalogue.

A mortal, such as you, can safely carry only one magic item. You therefore aim to get the most precious one. And obtain it you would, if not for a malicious, magical creature, known as The Imp.

The Imp can cast a mischievous spell, which transforms the content of any magic box into worthless dust. Of course, he will use the spell just after you buy a box, to make you pay for the item and not get it. You are thus forced to buy another box, and then the next one…

The Imp has enough magic to cast the spell at most $k$ times. He can, of course, refrain from using it, allowing you to keep an item. You can walk away at any time, empty-handed (though it would surely be a disgrace). However, if you get an item, you must keep it and leave the shop. You aim to maximize your gain (the value of the acquired item minus all the expenses paid previously), while The Imp wants to minimize it. If both you and the creature use the optimal strategy, how much gold will you earn?

Input

The first line of input contains the number of test cases $T$ ($1 \leq T \leq 5$). The descriptions of the test cases follow:

Each test case starts with a line containing the number of items $n$ ($1 \leq n \leq 150\, 000$) and the the maximum number of The Imp’s spells $k$ ($0 \leq k \leq 9$). The next $n$ lines contain the items’ values and costs, the $i$-th line containing the numbers $v_ i$ and $c_ i$, in that order ($0 \leq v_ i, c_ i \leq 10^6$).

Output

For each test case, output one line containing your gain.

1
3 1
10 5
8 1
20 12

7