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à: $$\begin{cases} a_{i_1} < a_{i_2} < \dots < a_{i_k} \\ 1 \le i_1 < i_2 < \dots < i_k \le n \end{cases}$$

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 \times 10^5)~.

• ~n~ dòng tiếp theo, dòng thứ ~i~ ~(i=1 \dots n)~ chứa ~2~ số nguyên dương ~a_i~ ~(a_i \le 10^9)~ và ~w_i~ ~(w_i \le 10^6)~. 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 thoả mãn yêu cầu bài toán.

Scoring

Sample Input 1

4
1 5
1 3
5 6
5 7

Sample Output 1

12

Notes

Chọn hộp phần thưởng thứ ~1~ và thứ ~4~ có tổng trị giá bằng ~12~.