Nhân dịp kỷ niệm 100 năm ngày thành lập công ty, để ghi nhận sự cống hiến của các thành viên, công ty tổ chức chương trình trao thưởng cho tất cả các nhân viên. Ban tổ chức chuẩn bị sẵn \(n\) hộp phần thưởng, mỗi hộp được đặt trên một bàn, các bàn đánh số từ \(1\) đến \(n\). Trên hộp phần thưởng thứ \(i\) (\(i = 1 \dots n\)) có dán nhãn là \(a_i\) và trong đó có phần thưởng trị giá \(w_i\).

Nhân viên có thể chọn một hay nhiều hộp phần thưởng liên tiếp hay không liên tiếp từ hộp phần thưởng ở bàn \(1\) đến bàn \(n\), hộp phần thưởng chọn sau phải có nhãn lớn hơn nhãn trên hộp phần thưởng chọn trước, tức là:

Yêu cầu: Bạn hãy giúp nhân viên chọn cho mình các hộp phần thưởng để có tổng trị giá là lớn nhất.

Input

• Dòng 1: Chứa số nguyên dương \(n\) (\(n \le 5 \cdot 10^5\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) (\(i = 1 \dots n\)) chứa hai số nguyên dương \(a_i\) (\(a_i \le 10^9\)) và \(w_i\) (\(w_i \le 10^9\)). Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

• Một số nguyên duy nhất thỏa mãn yêu cầu bài toán.

Example

4
1 5
1 3
5 6
5 7

12

Scoring

• Subtask 1 (60% số điểm): \(n \le 10^3\).
• Subtask 2 (40% số điểm): \(10^3 < n \le 5 \cdot 10^5\).