Tý có một khu rừng có \(N\) cây được trồng thành hàng dọc theo một con đường. Cây thứ \(i\) nặng \(w_i\) tấn và nằm ở vị trí \(d_i\) (tính từ đầu con đường).

Người ta muốn xây dựng hai xưởng cưa ở hai vị trí bất kỳ (có thể trùng với vị trí cây hoặc không). Mỗi cây sẽ được vận chuyển đến xưởng cưa gần nhất về phía trái (nghĩa là xưởng cưa đầu tiên ở bên trái cây đó). Cây nào không có xưởng cưa nào ở bên trái thì phải vận chuyển đến xưởng cưa đầu tiên.

Chi phí vận chuyển cây \(i\) đến xưởng cưa ở vị trí \(p\) là \(w_i \times (d_i - p)\).

Hãy chọn vị trí đặt hai xưởng cưa (kể cả vị trí đầu con đường) để tổng chi phí vận chuyển là nhỏ nhất.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 20000\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(d_i, w_i\) (\(0 < d_1 < d_2 < \dots < d_N \le 2 \times 10^6, 1 \le w_i \le 10^4\)).

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí nhỏ nhất.

Ví dụ

Input:

4
1 3
5 2
6 3
10 4

Output:

14

Giải thích: Đặt xưởng ở vị trí \(5\) và \(10\). Cây 1,2 đến xưởng ở 5: \(3*(5-1)+2*(5-5)=12\). Cây 3,4 đến xưởng ở 10: \(3*(10-6)+4*(10-10)=12\). Tổng \(24\). Tối ưu hơn: xưởng ở \(1\) và \(6\): \(0+2*(6-5)+3*(6-6)+4*(10-6)=2+0+16=18\).

Ràng buộc

• Subtask 1 (30%): \(N \le 500\).
• Subtask 2 (30%): \(N \le 5000\).
• Subtask 3 (40%): \(N \le 20000\).