Magic Shoppe Treasure Game

You enter Ye Olde Magic Shoppe with a bag of hard‐earned gold and a single chance to acquire a precious magic item. There are \(n\) magic boxes in the shop; the \(i\)th box costs \(c_i\) gold pieces to buy and contains an item worth \(v_i\) gold pieces. You know all the costs and values from the ancient catalogue.

You can carry only one magic item. However, a mischievous creature called The Imp lurks in the shop. Every time you buy a box, the Imp may cast a spell that turns the item inside into worthless dust. The Imp can cast his spell at most \(k\) times in total. If he does cast the spell on a box, you lose the gold you paid and must try another box; if he refrains, you keep the item and must leave immediately, incurring all the costs of the boxes you bought along the way.

Your gain is calculated as the value of the magical item you finally keep minus the sum of all costs you have paid for all boxes purchased (including those spoiled by the Imp). You may also choose to walk away with nothing (gain 0) at any time. Assuming both you and The Imp play optimally (you maximize your gain and The Imp minimizes it), determine the maximum gold you can guarantee to earn.

Game Theoretic Explanation: Since The Imp can spoil at most \(k\) boxes, if you want to secure an item you must be prepared to purchase \(k+1\) boxes. In the optimal strategy you select a sequence of \(k+1\) boxes. Let the final accepted box be the one you keep. Your net gain is the value of that box minus the total cost of all \(k+1\) boxes purchased. Because The Imp is adversarial, he will spoil boxes in such a way as to force you to incur the minimum possible cost saving. Equivalently, for each candidate box \(i\) that you might eventually keep, your guaranteed gain if you use it as the final box is \[ \text{gain}_i = (v_i - c_i) - S_i, \] where \(S_i\) is the sum of costs of \(k\) boxes chosen (with the smallest possible costs) from the remaining boxes (i.e. excluding box \(i\)). You want to maximize this gain over all candidates and if no positive gain is possible, you walk away with 0.

Note: If \(k \ge n\) then you have to buy all boxes if you want one item, so in that case treat \(k = n-1\) (i.e. you buy all boxes and use all other boxes as spoilt ones).

inputFormat

The input begins with a line containing two integers \(n\) and \(k\) (the number of boxes and the maximum number of spells The Imp can cast respectively).\

Then follow \(n\) lines. The \(i\)th of these contains two integers \(c_i\) and \(v_i\) — the cost to purchase the \(i\)th box and the value of the item inside it.

outputFormat

Output a single integer: the maximum gold you will earn if both you and The Imp play optimally.

sample

3 1
5 10
2 6
3 5

3