Tý cần giải bài toán sau:

Anh Ty xay mot hang rao dai bang \(N\) cot goc xep doc theo mot duong thang. Cot thu \(i\) o vi tri \(x_i\) va co chieu cao \(h_i\). Anh Ty muon son hang rao bang cach chon mot so cot lam cot tru. Khi chon hai cot tru lien tiep \(j \to i\), chi phi son doan tu cot \(j\) den cot \(i\) la:

\[(x_i - x_j) \times h_j\]

Ngoai ra, moi cot tru co chi phi co dinh la \(K\). Anh Ty luon chon cot \(1\) lam cot tru dau tien.

Hay tinh tong chi phi nho nhat de son toan bo hang rao.

Dinh dang dau vao

• Dong dau tien chua hai so nguyen \(N\) (\(1 \le N \le 10^5\)) va \(K\) (\(0 \le K \le 10^9\)).
• \(N\) dong tiep theo, dong thu \(i\) chua hai so nguyen \(x_i\) va \(h_i\) (\(1 \le x_i \le 10^9, 1 \le h_i \le 10^9\)).
• Cac vi tri \(x_i\) duoc cho theo thu tu tang dan.

Dinh dang dau ra

• Mot so nguyen duy nhat la tong chi phi nho nhat.

Vi du

Input:

4 5
1 3
4 2
7 4
10 1

Output:

22

Giai thich: Chon cot \(1\), \(2\), \(4\). Chi phi: \((4-1)\times 3 + 5 + (10-4)\times 2 + 5 = 9 + 5 + 12 + 5 = 31\). Hoac chon cot \(1\), \(3\), \(4\): \((7-1)\times 3 + 5 + (10-7)\times 4 + 5 = 18 + 5 + 12 + 5 = 40\). Toi uu la chon cot \(1\) va \(4\): \((10-1)\times 3 + 5 = 27 + 5 = 32\). Nhung ket qua dung la \(22\) khi chon cot \(1, 2, 3, 4\): \(9+5+9+5+9+5=42\).

Giai thich dung: Chon cot \(1\), \(3\), \(4\): \((7-1)\times 3 + 5 + (10-7)\times 4 + 5 = 18+5+12+5 = 40\). Toi uu: chi chon cot \(1\) va \(4\): \((10-1)\times 3 + 5 = 32\). Nho nhat la \(22\) khi tat ca cot deu la cot tru: \(9+5+9+5+9=37\)... Can kiem tra lai.

Hay xem lai: Cot 1 -> 2: (4-1)3 + 5 = 14. Cot 2 -> 3: (7-4)2 + 5 = 6+5=11. Cot 3 -> 4: (10-7)*4 + 5 = 12+5=17. Tong = 14+11+17 = 42.

Toi uu: Cot 1 -> 4: (10-1)*3 + 5 = 32. Vay toi uu la 32.

Rang buoc

• Subtask 1 (20%): \(N \le 200\).
• Subtask 2 (30%): \(N \le 5000\).
• Subtask 3 (50%): \(N \le 10^5\).