Trong kỳ thi chọn học sinh giỏi cấp tỉnh năm học 2022 - 2023, để độ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}~</p>

~1 \le i_1<i_2<\dots<i_k \le n~</p>

Yêu cầu: Em hãy chọn cho mình các món quà để có tổng trị giá là lớn nhất.

Input

• Dòng đầu 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 hai 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~.

Output

Ghi 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

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

• Ở 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~ có tổng trị giá là ~3+10+12=25~.