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

• Chọn một điểm xuất phát là một trong N vị trí đã cho.

• Chiều nhảy theo chiều tia Ox hoặc ngược lại.

• Chiều nhảy của các bước nhảy phải giống nhau

• Độ dài bước nhảy sau phải lớn hơn hoặc bằng bước nhảy trước, và phải nguyên dương. Không được nhảy quá N bước nhảy.

• Nhảy vào vị trí nào, sẽ lấy điểm tại ví vị trí đó.

Yêu cầu: Tìm cách nhảy để có tổng điểm lớn nhất.

Input:

• Dòng 1: chứa 1 số N ( 1 ≤ N ≤ 1000);

• N dòng tiếp theo, mỗi dòng chứa 2 số X[i], P[i], ( 1 < X[i], P[i] ≤ 1000000)

Output:

Ghi tổng điểm lớn nhất tìm được

Sample Input

6
5 6
1 1
10 5
7 6
4 8
8 10

Sample Output

25