Để 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 ; 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.

Input

• Dòng 1: Số nguyên dương ~n~ ~(n \le 10^5)~.

• ~n~ dòng tiếp theo, dòng thứ ~i~ 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

• Một số nguyên duy nhất bằng tổng năng lực thi đấu của các Robot được chọn.

Scoring

Sample Input 1

5
5 16
3 6
4 5
5 2
2 8

Sample Output 1

16

Sample Input 2

5
4 10
1 3
5 15
3 10
4 12

Sample Output 2

25

Notes

Test 1: Chọn Robot thứ nhất, tổng năng lực thi đấu là ~16~.

Test 2: Có thể chọn các Robot thứ 1, 3 để có tổng năng lực thi đấu là: ~10 + 15 = 25~. Hoặc có thể chọn các Robot thứ 2, 4, 5 để có tổng năng lực thi đấu là: ~3 + 10 + 12 = 25~. Kết quả in ra là ~25~.