Để chuẩn bị cho giải đấu Robot toàn quốc, đội của Thư dự định mua một số Robot từ doanh nghiệp XBOT. Doanh nghiệp này trưng bày một dãy Robot được đánh số từ \(1\) đến \(n\) (từ trái qua phải). Robot thứ \(i\) được dán nhãn mức tiêu thụ năng lượng \(p_i\) và có năng lực thi đấu \(w_i\).

Đội của Thư nhờ chuyên gia chọn lần lượt từ trái qua phải một hoặc nhiều Robot thỏa mãn điều kiện: Robot chọn sau phải có nhãn mức tiêu thụ năng lượng lớn hơn Robot chọn trước (\(p_i < p_j\) với \(i < j\)) và tổng năng lực thi đấu của các Robot được chọn là lớn nhất.

Yêu cầu

Hãy viết chương trình giúp chuyên gia tìm ra phương án chọn Robot thỏa mãn điều kiện đặt ra sao cho tổng năng lực thi đấu là lớn nhất.

Input

• Dòng 1: Số nguyên dương \(n\) (\(n \le 5 \cdot 10^5\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) (\(i = 1 \dots n\)) có hai số nguyên dương \(p_i\) (\(p_i \le 10^9\)) và \(w_i\) (\(w_i \le 10^6\)) tương ứng là nhãn mức tiêu thụ năng lượng và năng lực thi đấu của Robot thứ \(i\), mỗi số cách nhau một dấu cách trống.

Output

• Ghi ra một số nguyên duy nhất là tổng năng lực thi đấu lớn nhất của các Robot được chọn.

Example

5
5 16
3 6
4 5
5 2
2 8

16

5
4 10
1 3
5 15
3 10
4 12

25

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(10^3 < n \le 5 \cdot 10^5\).