Trên một bàn cờ kích thước vô hạn, bạn đặt một quân cờ đặc biệt tên là “Barons” tại vị trí ~(0,0)~. Barons sẽ di chuyển theo hai quy tắc sau:

• Tại bước đầu tiên, Barons di chuyển đến ô ~(K1,1)~ với ~K1~ là một số nguyên dương
• Tại bước thứ ~i~, Barons di chuyển từ ô ~(x,y)~ đến ô ~(x + Ki,y + 1)~, với điều kiện ~Ki~ là một số nguyên dương lớn hơn ~K(i – 1)~.

Nếu Barons di chuyển vào một ô chứa tiền xu, nó sẽ bỏ túi đồng xu đó. Hãy tính xem Barons có thể bỏ túi được nhiều nhất bao nhiêu đồng xu?

Input

• Dòng 1: một số nguyên ~N (0 < N \le 50)~ là số đồng xu
• Dòng ~2..N + 1~: Mỗi dòng chứa hai số nguyên ~(x[i],y[i])~ là tọa độ của đồng xu thứ ~i, 0 < x[i],y[i] \le 10000~.

Output

• 1 dòng duy nhất: số đồng xu tối đa Baron có thể bỏ túi

Sample

Input #1

3
15 4
5 5
30 6

Output #1

2

Input #2

1
10 10

Output #2

0

Input #3

6
1 1
3 2
6 3
10 4
15 5
21 6

Output #3

6

Problem source: Kc97ble - Free Contest 20