Turning Off Streetlights

There are N streetlights on a long road, listed in order of position. Each streetlight consumes a fixed amount of power per second while it is on. At time 0, a robot stands directly under streetlight M and can turn that streetlight off immediately.

The robot moves at 1 meter per second, and the time needed to turn off a streetlight is considered 0. If a streetlight with power consumption W is turned off at time t, then the wasted power caused by that streetlight is W × t.

Choose the order in which the robot turns off all streetlights so that the total wasted power is as small as possible. Output that minimum value.

The first line contains two integers N and M. N is the number of streetlights, and M is the number of the streetlight where the robot starts.

Each of the next N lines contains two integers D and W for one streetlight: its position D and its power consumption per second W. The value D is the distance from the start of the road and satisfies 0 ≤ D ≤ 1,000. The value W satisfies 1 ≤ W ≤ 100,000,000.

The streetlights are given in increasing order of position D and are numbered 1 through N in input order. The constraint 1 ≤ N ≤ 1,000 holds.

The minimum wasted power is always less than 1,000,000,000.

Output one integer: the minimum possible wasted power.