Trong kỳ thi 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ả các thí 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 mặt bàn, các bàn được đánh số thứ tự từ 1 đến \( n \). Trên hộp quà thứ \( i \) có dán nhãn \( a_i \) và trong đó có món quà giá trị là \( 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 thứ \( n \), hộp quà chọn sau phải có nhãn lớn hơn hộp quà chọn trước, tức là:

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

Dữ liệu

Đọc từ file văn bản QUA.INP gồm:

• Dòng 1: số nguyên dương \( n \) (\( n \leq 5.10^5 \));
• \( n \) dòng tiếp theo, dòng thứ \( i \) (\( i = 1..n \)) ghi hai số nguyên dương \( a_i \) (\( a_i \leq 10^9 \)) và \( w_i \) (\( w_i \leq 10^6 \)) là nhãn và giá trị của món quà trong hộp quà thứ \( i \).

Kết quả

Ghi ra file văn bản QUA.OUT là số nguyên duy nhất là tổng giá trị các món quà được chọn.

Ví dụ

Giới hạn

• Subtask 1: có 10/30 test tương ứng 1 điểm với \( n \leq 10^3 \);
• Subtask 2: có 20/30 test tương ứng 3 điểm với \( n \leq 5.10^5 \).