Nissy sees \(n\) boxes lying on a straight line. He knows the weight and position of each box. Now Nissy wants to pile up the boxes into \(k\) number of stacks/groups but with certain limitations:

• Boxes can only be moved from right to left

• Stacking/grouping of boxes can only be done at positions where there exists at least one box in the given initial configuration

• A valid group/stack should have at least \(1\) box

The image given below shows how the boxes are piled into two stacks at position \(5\) and \(55\)

For moving a box \(i\) of weight w(i) from position \(x(i)\) to position \(x(j)\) where \( x(i)>x(j)\), magnitude of amount of work = \(w(x(i)-x(j))\) needs to be done. Nissy asks you to determine the minimum amount of work he needs to do to rearrange the boxes into \(k\) groups/stacks. Assume the work done to place a box on top of another is negligible.

Input Format:

First Line: \(n\)(the number of boxes) and \(k\)(the number of groups needed)
Each of the next n lines includes two integers\( x(i)\)=position of the \(i\) th box and \(w(i)\) = weight of the \(i\) th box.

Output Format:

Print the minimum work needs to be done to rearrange the boxes into \(k\) groups.

Constraints:
\(1 \le k < n \le 5000\)
\(1 \le w(i),x(i) \le 10^6\)