Hoàng tử Ếch đang ở bờ này của con sông, phải nhảy được sang bờ bên kia - nơi công chúa đang bị mụ phù thủy giam giữ - để giải thoát cho nàng. Để làm việc này, hoàng tử phải nhờ đến một số trong số \(N\) lá sen vốn được giăng thành hàng ngang trên mặt sông. Hoàng tử, xuất phát từ bờ bên này, chỉ có thể nhảy đến các lá sen phía trước mặt (không được nhảy giật lùi) hoặc nhảy thẳng sang bờ bên kia nếu muốn, lần lượt qua các lá sen (nếu cần) để rồi kết thúc được tại bờ bên kia. Việc nhảy như vậy phải tuân thủ quy tắc: nếu tổng số bước nhảy lớn hơn \(1\) thì mỗi bước nhảy sau không được dài hơn bước nhảy trước đó.

Xem vị trí của hoàng tử (bờ bên này) và công chúa (bờ bên kia) cùng với mỗi lá sen như một điểm trên trục số: bờ bên này có tọa độ \(0\), bờ bên kia có tọa độ \(x_{N+1}\), lá sen \(i\) có tọa độ \(x_i\) \((i = 1, 2, ...,N)\) thỏa điều kiện: \(0 \lt x1 \lt ... \lt x_N \lt x_{N+1}\).

Trong quá trình nhảy, hoàng tử Ếch được tăng cường thêm sinh lực nhờ tận hưởng hết số muỗi thần có trên lá sen đặt chân đến: lá sen \(i\) có \(M_i\) con muỗi như vậy \((i = 1, 2, ..., N)\). Đương nhiên, hoàng tử rất muốn mình dồi dào sinh lực nhất có thể tại thời điểm gặp được công chúa nhờ việc tận hưởng được số muỗi nhiều nhất \(M_{max}\).

Yêu cầu

• Hãy viết chương trình xác định giá trị của \(M_{max}\).

Dữ liệu vào

• Gồm \(N+2\) dòng có cấu trúc như sau:
• Dòng đầu ghi một số nguyên \(N\) \((1 \le N \le 500)\)
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo ghi hai số nguyên \(x_i , M_i\) (cách nhau bởi khoảng trống) tương ứng là tọa độ và số muỗi của lá sen \(i\) \((1\le x_i \le 10^6, 1 \le M_i \le 10^9, i = 1, 2, ..., N)\).
• Dòng thứ \(N+2\) (dòng cuối cùng) ghi số \(x_{N+1}\).

Dữ liệu ra

• Số nguyên duy nhất \(M_{max}\) tìm được.

Input 1

5 
2 4 
6 5 
7 3
10 6 
12 5 
17

Output 1

10

Ràng buộc:

• 60% số test ứng với 60% số điểm của bài ứng với N \le 20.
• Giới hạn thời gian cho mỗi test: 01 giây.