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

\(a_{i_1} < a_{i_2} < a_{i_3} < ... < a_{i_k}\) và \(1 \le i_1 < i_2 < i_3 < ... < i_k \le n\)

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

• Dòng 1: số nguyên dương \(n\) \((n \le 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 \le 10^9)\) và \(w_i (w_i \le 10^6)\) là nhãn và giá trị của món quà trong hộp quà thứ \(i\).

Dữ liệu ra:

• Ghi ra một 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 ứng với 1 điểm \(n \le 10^3\)
• Subtask 2: có 20/30 test ứng với 3 điểm \(n \le 5.10^5\)