Minimizing Truck Travel Distance

Yong manages m trucks and has n transportation stations located between City A and City B. City A is located at coordinate \(0\) and City B is at coordinate \(x\). Each station \(i\) is located at \(p_i\) (with \(0 < p_i < x\)) and can serve as the starting station for at most \(c_i\) trucks.

When a truck delivers goods, it departs from its designated station, goes to either City A or City B, and returns to the station. The round-trip distance when delivering to City A is \(2p_i\), and for City B it is \(2(x-p_i)\). A truck will always choose the destination that minimizes its travel distance, i.e. its individual cost is \(\min(2p_i, 2(x-p_i))\).

The task is to assign each of the \(m\) trucks to a station (without exceeding the station capacities) so that the total daily travel distance of all trucks is minimized. Output this minimum total distance.

You can assume that the total station capacity is at least \(m\) (i.e., \(\sum_{i=1}^{n} c_i \ge m\)).

inputFormat

The first line contains three integers \(m\), \(n\), and \(x\) separated by spaces.

The next \(n\) lines each contain two integers \(p_i\) and \(c_i\) separated by a space, representing the position of station \(i\) and its capacity respectively.

\(1 \le m \le 10^5\), \(1 \le n \le 10^5\), \(1 \le p_i < x \le 10^9\), and \(1 \le c_i \le 10^5\).

outputFormat

Output a single integer: the minimum total daily travel distance of all \(m\) trucks.

sample

3 2 10
2 2
8 3

12