Vận chuyển gỗ

Trên một con đường dốc, có \(n\) cây cổ thụ cần được đốn hạ và vận chuyển đến các nhà máy cưa. Các cây được đánh số từ \(1\) đến \(n\) từ trên xuống dưới. Vận chuyển chỉ có thể theo một hướng duy nhất là từ trên xuống dưới theo con dốc.

Ban đầu, chỉ có một nhà máy cưa nằm ở đáy dốc. Chính quyền địa phương quyết định xây thêm hai nhà máy cưa nữa dọc trên con đường đó. Nhiệm vụ của bạn là xác định vị trí của hai nhà máy cưa mới để tổng chi phí vận chuyển là nhỏ nhất.

Chi phí vận chuyển của một cây là tích của khối lượng gỗ của cây đó nhân với quãng đường vận chuyển. Tổng chi phí vận chuyển là tổng chi phí của tất cả các cây. Mỗi cây sẽ được vận chuyển đến nhà máy cưa gần nhất nằm ở phía dưới nó.

Với vị trí và khối lượng của \(n\) cây cổ thụ, hãy tìm vị trí tối ưu để đặt thêm hai nhà máy cưa nhằm đạt được tổng chi phí vận chuyển nhỏ nhất.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)), là số cây cổ thụ.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i\) và \(d_i\) (\(0 \le w_i, d_i \le 10^4\)), trong đó \(w_i\) là khối lượng của cây thứ \(i\) và \(d_i\) là khoảng cách từ cây thứ \(i\) đến cây thứ \(i+1\). Giá trị \(d_n\) là khoảng cách từ cây thứ \(n\) đến đáy dốc.

Output

In ra một số nguyên duy nhất là tổng chi phí vận chuyển nhỏ nhất có thể.

Example

9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

26

Scoring

• Subtask \(1\) (\(30\%\) số điểm) : \(1 \leq n \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm) : \(1 \leq n \leq 1000\).
• Subtask \(3\) (\(40\%\) số điểm) : không có ràng buộc gì thêm.