Trong kỳ thi chọn học sinh giỏi tại trại hè Hùng Vương, để động viên, khích lệ tinh thần cho học sinh ban tổ chức có chương trình tặng quà cho tất cả học sinh tham dự kỳ thi. Ban tổ chức chuẩn bị sẵn ~n~ hộp đựng quà, 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 quà thứ ~i~ ~(i = 1 \dots n)~ có dán nhãn là ~a_i~ và trong đó có món quà trị giá ~w_i~. Học sinh có thể chọn một hay nhiều hộp quà liên tiếp hay không liên tiếp từ hộp quà ở bàn ~1~ đến bàn ~n~, hộp quà chọn sau phải có nhãn lớn hơn nhãn trên hộp quà chọn trước, tức là:

~a_{i_1} < a_{i_2} < \dots < a_{i_k}~

~1 \le i_1 < i_2 < \dots < i_k \le n~

Em hãy chọn cho mình món quà có tổng trị giá là lớn nhất.

Input

• Dòng ~1~ ghi 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)~ ghi ~2~ số nguyên dương ~a_i~ ~(a_i \le 10^9)~ và ~w_i~ ~(w_i \le 10^6)~ là nhãn và trị giá của món quà trong hộp ~i~. Các số trên cùng dòng cách nhau ít nhất một khoảng trống.

Output

Ghi ra một số duy nhất là tổng trị giá các món quà được chọn.

Scoring

Sample Input 1

5
5 15
3 5
4 7
5 1
2 8

Sample Output 1

15

Sample Input 2

5
4 10
1 3
5 15
3 10
4 12

Sample Output 2

25

Notes

Trong ví dụ thứ nhất, chọn hộp quà thứ ~1~ có trị giá bằng ~15~.

Trong ví dụ thứ hai, có thể chọn các hộp quà thứ ~1, 3~ có tổng trị giá là ~10 + 15 = 25~ hoặc chọn các hộp quà thứ ~2, 4, 5~.