Problem D
Peak Tram

Inspired by the Peak Tram in Hong Kong, you are going to build your own peak tram on a hill, together with the buildings near it. The peak tram and the buildings are aligned on a straight line. The peak tram is at position $0$ on the line. There are $n$ buildings, where building $i$ is at position $i$ on the line ($i=1,2,\dots ,n$). Let the height of building $i$ be $h_ i$. The peak tram starts ascending from height $0$, and the passengers would look at the building that first touches the horizontal ray from the peak tram at the current height. In other words, building $i$ is visible some time during the ascent if and only if $h_ i > h_ j$ for all $j < i$ (i.e., no other buildings are blocking the sight). Assume the hill is sufficiently tall so the peak tram can always ascend to at least the height of the tallest building.

Figure 1: The figure shows the peak tram (leftmost) and $5$ buildings. The buildings in grey are visible during the ascent. It demonstrates an optimal answer to the sample input, with resultant heights of $5, 6, 4, 9, 6$.

You want the passengers to enjoy the view from the peak tram, so there should be at least $k$ buildings that are visible some time during the ascent. However, the problem is that you do not have any building yet, and you now have to build those $n$ buildings (i.e., you have to choose $h_ i$). Each building $i$ has a preferred height $p_ i$ and a cost per height difference $c_ i$. The cost for making the height of building $i$ to be $h_ i$ is given by $|h_ i - p_ i| \times c_ i$. Also the heights $h_ i$ you choose must be positive integers. Your task is to determine the minimum total cost so that at least $k$ buildings are visible during the ascent.

Input

The first line of the input contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 70$). Each of the following $n$ lines contains two integers $p_ i$ and $c_ i$ ($1 \leq p_ i \leq 10^9$, $1 \leq c_ i \leq 1\, 000$).

Output

Output one integer, the minimum total cost so that at least $k$ buildings are visible during the ascent.

5 3
5 3
3 2
4 8
9 4
6 2

6