P1220 Turning Off Streetlights

A village installed $n$ streetlights along a road. Each light has a different power rating (that is, they consume different amounts of electricity over the same period). Old Zhang lives next to one of the streetlights somewhere in the middle of this road. His job is to turn off these streetlights one by one every morning at daybreak. To save electricity for the village, Old Zhang recorded each streetlight’s position and power. Whenever he turns off the lights, he always walks as fast as possible. However, he does not know the order that minimizes the total electricity consumption. Every day at daybreak, he first turns off the streetlight at his own location, then he may go left or right to turn off other lights. At first, he thought to first sum the total power on the left and on the right, choose the side with the larger total power to turn off first, then go back to turn off the other side. In fact, this is not always optimal, because turning back at suitable moments during the process may save more. You are given that Old Zhang’s walking speed is $1m/s$, and each streetlight’s position (an integer, the distance from the starting point of the route, in $m$) and power ($W$). The time he spends switching off a light is very short and can be ignored. Please write a program to arrange the order of turning off the lights so that, measured from the moment Old Zhang starts, the total energy consumed by all lights is minimized (after a light is turned off, it no longer consumes power).

The first line contains two numbers $n$ (the total number of streetlights) and $c$ (the index of the streetlight where Old Zhang is located). The next $n$ lines each contain two values, giving the position and power of the $1$-st through $n$-th streetlight. The positions are guaranteed to be strictly increasing.

Output one number: the minimal energy consumption (unit: $J$, $1J=1W\times s$).

### Sample Explanation In this case, the turning-off order is `3 4 2 1 5`. ### Constraints $1\le n\le 50$，$1\le c\le n$，$1\le W_i \le 100$。 Translated by ChatGPT 5