Arranging Heaps

A mining company extracts a rare metal from river sand at $N$ mining points along the Long River. Each mining point is identified by its distance from the river's source, and produces one heap of mineral ore.

To collect the ore, the company regroups the $N$ heaps into a smaller number of $K$ heaps, each located at one of the original mining points. A very large barge does the moving: it starts at the source and can only travel downriver, so a heap produced at mining point $X$ may be carried to mining point $Y$ only if $Y > X$. Each heap is either moved in full to another mining point or left in place. Moving a heap of weight $W$ from mining point $X$ to mining point $Y$ costs $W \times (Y - X)$; a heap left in place adds nothing to the cost. The total regrouping cost is the sum of the costs of all heap movements.

Given $N$, $K$, the positions of the mining points, and the weight produced at each, compute the minimum total cost to regroup the $N$ heaps into exactly $K$ heaps.

The input contains several test cases; process test cases until the end of input.

Each test case begins with a line containing two integers $N$ and $K$ ($1 \le K < N \le 1000$): the number of initial heaps and the desired number of heaps after regrouping. Each of the next $N$ lines contains two integers $X$ and $W$ ($1 \le X, W \le 10^6$), meaning that a heap of weight $W$ was produced at mining point $X$. Within a test case the heaps are listed in strictly increasing order of their positions $X$.

For each test case, output a single line containing one integer: the minimum total cost to regroup the $N$ heaps into $K$ heaps.