The Imp

You walk into an old magic shop with hard earned gold, hoping to buy a wondrous item. The shop holds n items, each locked in a special magic box. Box i costs $c_i$ gold to buy and holds an item worth $v_i$ gold. You know every price and every value already, because you have read and memorized the old magic catalogue.

You can safely carry only one magic item, so you want the most precious one you can get. You would get it, if not for a spiteful magical creature called the Imp.

The Imp knows a spell that turns the contents of any magic box into worthless dust. He always casts it right after you buy a box, so that you pay for an item and receive nothing. You then have to buy another box, and then the next one.

The Imp has enough magic for at most k casts. He can also hold back and let you keep an item. You may walk away empty handed at any moment, although that would be a disgrace. Once you do receive an item, you must keep it and leave the shop. Your gain is the value of the item you carry out minus every gold piece you spent along the way. You want the gain as large as possible and the Imp wants it as small as possible. If both of you play optimally, how much gold do you earn?

The first line contains the number of test cases T. The test cases follow.

The first line of each test case contains the number of items n ($1 \le n \le 150000$) and the largest number of spells the Imp can cast, k ($0 \le k \le 9$). Each of the next n lines describes one item: line i contains the value $v_i$ and the cost $c_i$, in that order ($0 \le v_i, c_i \le 1000000$).

For each test case, print your gain on one line.