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

Yêu cầu: Hãy chọn các 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 \times 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~.

Output

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

Sample Input 1

5
5 15
3 5
4 7
5 1
2 8

Sample Output 1

15