677 . 切香腸問題
Description
恭喜你，現在成為了「英格蘭創意香腸」（Creative Sausages In England, CSIE）的董事長了！作為 CSIE 的董事長，你必須管理香腸工廠的製程與監督成本。你發現，如果有一條長度為 $l$ 的香腸被切成兩段，則所花費的成本就是這條香腸的長度。現在，就是想要計算一個長度為 $L$ 的香腸依照某種順序切若干段後的總成本。
如果將這一條香腸想像成左端在數線的 $0$ 處、右段在數線的 $L$ 處的話，則可以想像有 $N$ 次切割的動作，第 $i$ 次會切在某一個位置 $x_i$。請注意，不會有兩次的切割在一樣的地方，亦即 $x_i$ 是兩兩相異的。
譬如說，我有一個長度為 $4$ 的香腸，我先後在上面 $1, 2$ 的位置切割，則第一刀後，一個長度為 $4$ 的香腸會變成一個長度為 $1$ 和一個長度為 $3$ 的香腸，而第二次切割後，會變成一個長度為 $1$、一個長度為 $1$，和一個長度為 $2$ 的香腸，總花費 $4 + 3 = 7$。如果反過來切的話，則花費為 $4 + 2 = 6$。
Input Format
輸入將有 $N + 1$ 行。第一行將有兩個數字 $N$（$1 \leq N \leq 2 \times 10^ 5$）與 $L$（$1 \leq L \leq 10^ 7$），分別代表切了幾刀與香腸總長度。接下來的第 $i$（$1 \leq i \leq N$）行會有兩個數字 $x$ $k$，代表第 $k$（$1 \leq k \leq N$）刀切在 $x$ （$0 \leq x \leq L$）的位子。保證所有的 $k$ 在 $[1, N]$ 內且兩兩相異，且所有 $x$ 兩兩相異。
此外，對於佔分 $20\%$ 的測試資料，額外保證 $N \leq 1000$，且對於另外佔分 $30\%$ 的測試資料，$N \leq 50000$。
Output Format
請輸出一個數字，代表最後的總時間花費。
Sample Input 1
1 1
2 2
Sample Output 1
Sample Input 2
2 1
1 2
Sample Output 2
Sample Input 3
7 3
1 4
2 1
71 5
22 2
Sample Output 3
Hints
Problem Source
此題出自 2021 年 1 月 APCS
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~10 | $1 \le N \le 1000$ | 20 |
| 3 | 0~2, 11~19 | $1 \le N \le 50000$ | 30 |
| 4 | 0~28 | 無額外限制 | 50 |