Optimal Street Light Shutdown

In a village, there are (n) street lights installed along a straight road. Each street light is located at an integer position (in meters from the start of the road) and has its own power rating (in Watts). Old Zhang lives next to one of these street lights which is located roughly in the middle of the road. Every morning at dawn he starts by switching off the street light next to his house (which turns off immediately, incurring no energy consumption afterwards) and then proceeds to turn off all the other street lights in some order. While he walks at a speed of (1 m/s) and the time to switch a lamp off is negligible, every lamp that is still on continues to consume energy (its power multiplied by the time elapsed since the start of his route).

The objective is to decide the order in which Old Zhang should travel in order to turn off all the lights so that the total energy consumed (i.e. the sum over each lamp of (\text{power} \times \text{time until switch-off})) is minimized. Note that once a lamp is switched off, it stops consuming energy.

Formally, assume the (n) street lights are given by their positions (x_0, x_1, \dots, x_{n-1}) (in increasing order) and corresponding power ratings (p_0, p_1, \dots, p_{n-1}). Old Zhang starts at the lamp with index (k = \lfloor n/2 \rfloor) (using 0-indexing) and that lamp is turned off at time (0) (so its power is not counted in the cost). For any subsequent lamp, if it is switched off at time (t) then its energy consumption is (p_i \times t). When moving from one lamp to the next, the travel time equals the absolute difference in positions.

Design a program that, given (n) and the details of the (n) street lights (each with its position and power), computes the minimum total energy consumed by all the lamps (except the starting one) by an optimal route of turning off the lights.

The problem can be solved by dynamic programming. Let the sorted street lights be numbered from (0) to (n-1) and assume that the starting lamp is index (k = \lfloor n/2 \rfloor). We use a DP state (dp[i][j][s]) where (i) and (j) (with (i \le j)) denote that the lamps in the range ([i,j]) (which includes the starting lamp) have been turned off. The parameter (s) is (0) if Old Zhang is currently at position (x_i) (left end) and (1) if he is at (x_j) (right end). Let (T) be the total power of all lamps except the starting lamp. At any state, the unvisited lamps contribute a waiting power equal to (T) minus the sum of the powers of the lamps already turned off. When moving from state (dp[i][j][s]) to a new state by extending to the left or right, the additional cost equals the travel time multiplied by the waiting power.

The final answer is (\min(dp[0][n-1][0],,dp[0][n-1][1])).

inputFormat

The first line contains a single integer (n) ((1 \le n \le 10^4)), the number of street lights. (n) lines follow; each line contains two integers (x) and (p) ((0 \le x \le 10^9), (1 \le p \le 10^4)), representing the position and power rating of a street light. It is guaranteed that all (x)'s are distinct. The street lights can be given in arbitrary order. Old Zhang starts at the lamp which is the (\lfloor n/2 \rfloor^{th}) smallest by position (0-indexed).

outputFormat

Output a single integer: the minimum total energy consumed (in Watt-seconds) from the time the turning off process begins until all lamps are turned off.

sample

1
100 50

0