Christmas Eve

Santa Corporation delivers presents to children all over the world between Christmas Eve night and Christmas morning. Every santa who volunteers for delivery receives one high tech sleigh, and the trunk of that sleigh is connected by a teleporter to a single warehouse of the supply department. A warehouse holds at most one teleporter, so each sleigh needs its own warehouse.

The supply department manages $n$ warehouses placed on a straight line. You must pick $k$ of them for the teleporters and move all presents from the remaining warehouses into the chosen ones.

Warehouse $i$ sits at position $x_i$ and holds $w_i$ tons of presents. The presents of one warehouse cannot be split, so they all move at once into one other warehouse. Moving $w$ tons from the warehouse at $x_i$ to the warehouse at $x_j$ costs $|x_i - x_j| \times w$.

Santa Corporation wants to spend as little as possible. Pick the $k$ warehouses so that the total moving cost is minimum, and report that cost.

The first line has the number of warehouses $n$ and the number of teleporters $k$ ($1 \le k < n \le 5000$).

Each of the next $n$ lines has the position $x_i$ of warehouse $i$ and the weight $w_i$ of the presents stored there ($1 \le x_i, w_i \le 1000000$).

The warehouses are not given in position order, and several warehouses can share one position.

Print the minimum total cost of moving every present into the $k$ chosen warehouses.