Cutting Cost (APCS 2021-01 Advanced)

There is a stick of length \(L\), and you will cut it \(n\) times.

Place the stick on a number line so that its left end is at position \(0\) and its right end is at position \(L\). Each cut is given as a number between \(0\) and \(L\): you cut the piece of stick passing through that position into two pieces, and the cost of the cut equals the length of the piece being cut.

For example, let \(L = 7\) and make \(3\) cuts. The 1st cut is at position \(3\); the stick is still whole, so the cost is \(7\). The 2nd cut is at position \(2\); the piece containing position \(2\) is \([0, 3]\), so the cost is \(3\). The 3rd cut is at position \(5\); the piece containing position \(5\) is \([3, 7]\), so the cost is \(4\). The total cost is \(7 + 3 + 4 = 14\).

Input

The first line contains two integers \(n\) and \(L\).

Each of the next \(n\) lines contains two integers \(x\) and \(i\), meaning that a cut is made at position \(x\) and it is the \(i\)-th cut overall. It is guaranteed that every \(i\) is an integer in \([1, n]\) and no two lines share the same \(i\); no two lines share the same position \(x\), and \(0 < x < L\).

Output

Output one integer: the total cutting cost. The answer may exceed \(2^{31}\) but never exceeds \(2^{60}\).

Scoring

• 20 points: \(1 \le n \le 1000\), \(1 \le L \le 10^7\)
• 30 points: \(1 \le n \le 50000\), \(1 \le L \le 10^7\)
• 50 points: \(1 \le n \le 200000\), \(1 \le L \le 10^7\)

Sample Input 1

3 7
2 2
3 1
5 3

Sample Output 1

14

Source

APCS January 2021, programming problem 3 "Cutting Cost"; also available as ZeroJudge f607.