Turning Off the Lamps

Dobrica has landed an interesting, well-paid job: every morning he must turn off all the street lamps in his village. The lamps stand in a single row on one side of a straight road.

After partying through the night, Dobrica begins right next to one of the lamps. Each lamp has a bulb of a fixed power, and while it is on it spends that much energy every second. Being very tired, Dobrica walks at a speed of 1 meter per second, and he switches a lamp off the instant he passes it (this takes no extra time).

Every lamp keeps spending energy until the moment Dobrica reaches it. Given the positions of the lamps, the power of each bulb, and the lamp Dobrica starts next to, find the minimum total energy that will be spent before every lamp is switched off.

The first line contains an integer N (2 ≤ N ≤ 1000), the number of lamps.

The second line contains an integer V (1 ≤ V ≤ N), the number of the lamp Dobrica starts next to.

Each of the next N lines describes one lamp with two integers D and W (0 ≤ D ≤ 1000, 0 ≤ W ≤ 1000): D is the lamp's distance in meters from the start of the village, and W is the power of its bulb (the energy it spends per second). The lamps are given in non-decreasing order of D.

Print a single integer: the minimum total energy that must be spent to turn every lamp off. The answer is always smaller than 1,000,000,000.