There are gold mines along a river, and each mine produces tons of gold. In order to collect the mined gold, we want to redistribute and consolidate it amongst exactly mines where it can be picked up by trucks. We do this according to the following rules:
- You can move gold between any pair of mines (i.e., and , where ).
- All the gold at some pickup mine must either stay at mine or be completely moved to some other mine, .
- Move tons of gold between the mine at location and the mine at location at a cost of .
Given , , and the amount of gold produced at each mine, find and print the minimum cost of consolidating the gold into pickup locations according to the above conditions.
Input Format
The first line contains two space-separated integers describing the respective values of (the number of mines) and (the number of pickup locations).
Each line of the subsequent lines contains two space-separated integers describing the respective values of (the mine's distance from the mouth of the river) and (the amount of gold produced in tons) for mine .
Note: It is guaranteed that the mines are will be given in order of ascending location.
Constraints
Output Format
Print a single line with the minimum cost of consolidating the mined gold amongst different pickup sites according to the rules stated above.
Sample Input 0
3 1
20 1
30 1
40 1
Sample Output 0
20
Explanation 0
We need to consolidate the gold from mines into a single pickup location (because ). The mines are all equidistant and they all produce the same amount of gold, so we just move the gold from the mines at locations and to the mine at for a minimal cost of .
Sample Input 1
3 1
11 3
12 2
13 1
Sample Input 1
4
Explanation 1
We need to consolidate the gold from mines into a single pickup location (because ). We can achieve a minimum cost of by moving the gold from mines and to the mine at .
Sample Input 2
6 2
10 15
12 17
16 18
18 13
30 10
32 1
Sample Output 2
182
Explanation 2
We need to consolidate the gold from mines into pickup locations. We can minimize the cost of doing this by doing the following:
- Move the gold from the mines at locations , , and to the mine at .
- Move the gold from the mine at location to the mine at .