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

\[\left\{ \begin{array}{r} a_{i_{1}} < \ a_{i_{2}} < \ldots < a_{i_{k}}\ \\ 1 \leq i_{1} < i_{2} < \ldots < i_{k} \leq n \end{array} \right.\ \]

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:

- Dòng 1 ghi số nguyên dương \(n\ (n \leq 5 \times 10^{5})\);

- \(n\) dòng tiếp theo, dòng thứ \(i\ (i = 1..n)\) ghi 2 số nguyên dương \(a_{i}\ (a_{i}\ \leq \ 10^{9})\) và \(w_{i}\ (w_{i}\ \leq \ 10^{6})\) là nhãn và trị giá của món quà trong hộp \(i\).

Kết quả:

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

Ví dụ:

Giới hạn:

- Có 10/30 test có \(n \leq \ 10^{3}\);

- Có 20/30 test có \(10^{3} < n \leq 5 \times 10^{5}\).