THPT Chuyên Bến Tre

            Trên trục tọa độ Ox có N vị trí được đánh dấu sẵn, vị trí i có tọa độ X_i . Xét một trò chơi như sau:

            Nhiệm vụ chính của bạn sẽ thực hiện các bước nhảy giửa các điểm đã đánh dấu. Trước khi bắt đầu trò chơi bạn phải chọn điểm bắt đầu (là một trong N vị trí đã đánh dấu) và chiều nhảy thuận theo chiều tia Ox hoặc ngược lại. Bạn được thực hiện số bước nhảy tùy ý với điều kiện chiều nhảy phải giống nhau và độ dài bước nhảy phải là một số dương và lớn hơn hoặc bằng bước nhảy liền trước. Tất nhiên với những điều kiện này bạn không thể thực hiện quá N bước nhảy. Mỗi vị trí i có một số điểm tương ứng là P_i, điểm của bạn là tổng số điểm các vị trí bạn đến được (bao gồm cả điểm xuất phát).

            Yêu Cầu: Tìm cách nhảy để đạt được số điểm lớn nhất.

Dữ Liệu:  Vào từ File 

-          Dòng đầu ghi số nguyên dương N (1<N<1000)

-          N dòng tiếp theo mỗi dòng thứ i ghi 2 số nguyên tương ứng là X_i, P­_i. (1<X_i, P_i<10⁶)

Kết Quả: Ghi ra File 

            Một số duy nhất là số điểm lớn nhất đạt được.

Example

Input:
6

5 6

1 1

10 5

7 6

4 8

8 10

Output:
25

Giải thích: Các vị trí nhảy qua: 4  5  7  10 (tương ứng điểm nhận được: 8+6+6+5=25)