切割費用 (APCS 2021-01 中高級)

有一根長度為 \(L\) 的棍子，你會把這個棍子切割 \(n\) 次。

假設一開始棍子左端放在數線上 \(0\) 的位置，棍子的右端放在數線上 \(L\) 的位置，每次的切割會給定一個介於 \(0\) 到 \(L\) 的數字表示要切割的位置，你要把穿過這個位置的棍子切成兩段，而所需的花費就等於所切割的棍子的長度。

例如棍子長度 \(L = 7\)，共切 \(3\) 次：第 \(1\) 刀切在位置 \(3\)，此時棍子完整，費用 \(7\)；第 \(2\) 刀切在位置 \(2\)，位置 \(2\) 所在的棍子是 \([0, 3]\)，費用 \(3\)；第 \(3\) 刀切在位置 \(5\)，位置 \(5\) 所在的棍子是 \([3, 7]\)，費用 \(4\)。總費用為 \(7 + 3 + 4 = 14\)。

輸入格式

第一行有兩個整數 \(n\)、\(L\)。

接下來 \(n\) 行每行有兩個整數 \(x\)、\(i\)，表示 \(x\) 位置被切過一刀，而這刀是全部的切割中的第 \(i\) 刀。保證 \(i\) 是介於 \([1, n]\) 的整數且不會重複，切割位置 \(x\) 也不會重複，且 \(0 < x < L\)。

輸出格式

輸出一個整數表示總共的切割費用，答案可能超過 \(2^{31}\) 但不會超過 \(2^{60}\)。

評分說明

• 20 分：\(1 \le n \le 1000\)，\(1 \le L \le 10^7\)
• 30 分：\(1 \le n \le 50000\)，\(1 \le L \le 10^7\)
• 50 分：\(1 \le n \le 200000\)，\(1 \le L \le 10^7\)

範例輸入 1

3 7
2 2
3 1
5 3

範例輸出 1

14

題目來源

APCS 2021 年 1 月實作題第 3 題。

題敘參考 ZeroJudge f607「切割費用」 整理，細節可能與正式試題有出入。