Minimizing Wood Transport Cost

There are n old trees planted in a straight line from the mountaintop to the mountain bottom. The local government has decided to cut them down. To avoid wasting any wood, every tree's wood is transported after being felled to a sawmill. However, wood can only be transported downhill.

A sawmill already exists at the bottom of the mountain. Two additional sawmills are planned to be built along the mountain road. Your task is to determine where to build these two sawmills (i.e. determine the partition of trees among the three sawmills) so that the total transportation cost is minimized. The transportation cost is calculated as one cent per kilogram per meter.

Note that if a group of trees is assigned to a sawmill, the optimal placement for that sawmill is at the position of the lowest tree in that group. In other words, if trees in the group have positions \(x_i, x_{i+1}, \dots, x_j\) (with \(x_i \ge x_{i+1} \ge \cdots \ge x_j\)), then the cost for that group is \[ \text{cost}(i,j)=\sum_{k=i}^{j} w_k\,(x_k-x_j), \] where \(w_k\) is the weight of the \(k\)-th tree. The overall goal is to partition the sequence of trees into three contiguous segments (when sorted in descending order of position) to minimize the total cost.

You are given the number of trees and for each tree its weight and position. You may assume that the trees can be re-ordered in descending order (so that the first tree is at the mountaintop and the last tree is at the mountain bottom). The sawmill at the bottom is fixed (its position is at the position of the last tree), and the other two sawmills can be placed optimally as explained.

inputFormat

The input begins with an integer \(n\) (\(1 \le n \le 10^5\) or as specified by the problem constraints), the number of trees. Each of the next \(n\) lines contains two integers \(w\) and \(x\), representing the weight (in kilograms) and the position (in meters) of a tree, respectively. The positions are arbitrary and may not be sorted; you should sort the trees in descending order of position (from mountaintop to mountain bottom) before processing.

outputFormat

Output a single integer: the minimum total transportation cost (in cents).

sample

3
10 100
20 50
30 0

0