Arranging Heaps

A mining company extracts terbium, a rare metal used to build lightweight magnets, from river sand. It mines the Long River at $N$ mining points, and each point is identified by its distance from the river source. Every mining point yields one heap of ore that is small in volume and high in value.

To collect the ore, the company regroups the $N$ heaps into a smaller number of $K$ heaps. Every new heap sits at one of the original mining points, and trucks pick the new heaps up from there.

The regrouping uses a barge. The barge is very large, so it can carry any amount of ore. It starts at the river source and travels downriver only, so the heap produced at mining point $X$ can be taken to a mining point $Y$ only if $Y > X$. Each heap is moved whole to another mining point, or it is left where it is. Moving a heap of weight $W$ from point $X$ to point $Y$ costs $W \times (Y - X)$. The total cost of the regrouping is the sum of the costs of the individual moves, and a heap that is not moved adds nothing to it.

Given $N$, $K$, the $N$ mining points, and the weight of the heap produced at each point, write a program that computes the minimum total cost of regrouping the $N$ initial heaps into $K$ heaps.

The first line contains two integers $N$ and $K$, the number of initial heaps and the number of heaps left after the regrouping ($1 \le K < N \le 1000$).

Each of the next $N$ lines describes one initial heap with two integers $X$ and $W$, meaning that mining point $X$ produced a heap of weight $W$ ($1 \le X, W \le 10^6$). The heaps are given in strictly increasing order of their mining points.

Print one integer on a single line, the minimum total cost of regrouping the $N$ initial heaps into $K$ heaps.