APCS202101 第3題切割費用

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

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

輸入說明

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

配分

20分: 1≤n≤1000,1≤L≤10^7

30分: 1≤n≤50000,1≤L≤10^7

50分: 1≤n≤200000,1≤L≤10^7

輸出說明

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

輸入範例

3 7

2 2

3 1

5 3

輸出範例

14

解題策略

使用map<起點,終點>與lower_bound(二分搜尋)