###### tags: `APCS`
# **f607－切割費用**
### **題目連結：** [**f607**](https://zerojudge.tw/ShowProblem?problemid=f607)
### **題目解析**
你有一根長度為𝐿的棍子，你需要將這根棍子切割𝑛次。每次切割的位置由一個整數表示，這個整數介於0 到𝐿之間。每次切割的費用是指切割後得到的兩段棍子的長度之和。
* 輸入參數講解：
* 第一行包含兩個整數𝑛和𝐿，分別表示切割次數和棍子的長度。
* 接下來的𝑛行，每行包含兩個整數𝑥和𝑖，其中𝑥表示切割位置，𝑖表示這是第𝑖刀。
### **解題方向**
* 初始化：將棍子的初始狀態設為 [0, L]，表示從位置 0 到位置 L 的整根棍子。
* 讀取輸入並排序：讀取𝑛和 𝐿。將每次切割的位置和順序存入一個列表 cuts，並按照切割順序排序。
* 切割並計算費用：
* 使用一個有序列表來維持目前的切割位置。
* 每次切割時，找到插入點，將新的切割點插入列表，並計算切割費用。
* 輸出結果：輸出總費用。
### **程式解析**

### **完整程式碼**

# f607: 切割費用
# 首先由測資排出切割的順序, 找到對應的切割位置後計算費用(該位置的前一個與後一個)
# ans => 累加每次「被切」的棍子長度
#
# 1次切割 => 0, 3, 7 => 7-0
# 2次切割 => 0, 2, 3, 7 => 3-0
# 3次切割 => 0, 2, 3, 5, 7 => 7-3

import bisect

# 讀取第一行輸入
N, L = map(int, input().split())

# 初始化棍子切割位置
stick = [0, L]

# 用來存儲每次切割的位置和順序
temp = []

# 讀取接下來的 N 行輸入
for i in range(N):
    row = list(map(int, input().split()))
    row[0], row[1] = row[1], row[0]  # 交換位置使其以切割位置排序
    temp.append(row)

# 按切割位置排序
temp.sort()

# 初始化總費用
ans = 0

# 進行每次切割並計算費用
for v in temp:
    idx = bisect.bisect_left(stick, v[1])  # 找到切割位置在現有棍子中的插入點
    stick.insert(idx, v[1])  # 插入切割位置
    ans += stick[idx+1] - stick[idx-1]  # 計算這次切割的費用

# 輸出總費用
print(ans)