시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB17151588.235%

문제

Dobrica get an interesting and well-paid job. Every morning he needs to turn off all the street lamps in his village. All the lamps are located on the same side of a straight road.

Dobrica is at the party every night until 5 AM and then he starts to turn off the lamps. In the beginning, he is standing besides one of them.

Every lamp has a light bulb of a defined power, and because Dobrica is ecologically conscious, he wants to turn off all the lamps in order that would minimize total energy spent.

Dobrica is moving at the speed of 1 m/s because he is very tired. Turning off a lamp does not take extra time because he can do it while passing by.
Write a program to calculate minimal energy that needs to be spent to turn all the lamps off for given locations of lamps, powers of light bulbs and

Dobrica's starting position.

입력

First line of the input file contains integer N, 2 ≤ N ≤ 1000, the number of lamps in the village.

Second line contains integer V, 1 ≤ V ≤ N, number of the lamp at which Dobrica started.

Each of the following N lines contains data describing a lamp - two integers D and W separated by a single space character, 0  D  1000, 0  W  1000. D is distance of a lamp from the beginning of the village (expressed in meters), and W is power of a light bulb in that lamp, i.e. the amount of energy spent by that light bulb during one second. Lamps are given in sorted order.

출력

First and only line of the output file should contain one integer - minimal amount of spent energy.

Note: the solution will always be smaller than 1,000,000,000.

예제 입력 1

3
2
1 4
6 5
9 7

예제 출력 1

65

예제 입력 2

4
3
2 2
5 8
6 1
8 7

예제 출력 2

56

예제 입력 3

6
5
3 2
11 10
12 18
13 19
15 15
17 19

예제 출력 3

370