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..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à:

                 ai₁ < ai₂ < … < ai_k   và 1 <= i₁ < i₂ < …< i_k <= n

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

* Dữ liệu vào: Đọc vào từ file văn bản QUA.INP gồm:

- Dòng 1 ghi số nguyên dương n (n 5.10⁵);

- n dòng tiếp theo, dòng thứ i (i=1..n) ghi 2 số nguyên dương a_i (a_i  10⁹) và w_i (w_i  10⁶) 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.

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