Hide

# 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.

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.

Sample Input 1 Sample Output 1
5 3
5 3
3 2
4 8
9 4
6 2

6

CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 6.2hard
Statistics Show