Trong một nỗ lực thiếu suy tính nhằm tăng khả năng di chuyển của cô bò cưng Bessie, Farmer John đã gắn một chiếc cà kheo lò xo vào mỗi chân của Bessie. Giờ đây Bessie có thể nhảy rất nhanh khắp trang trại, nhưng cô vẫn chưa học được cách giảm tốc.

Để giúp Bessie luyện tập khả năng kiểm soát bước nhảy tốt hơn, Farmer John dựng một đường tập dọc theo một lối đi thẳng một chiều qua trang trại. Tại nhiều vị trí đôi một khác nhau trên lối đi, ông đặt \(N\) mục tiêu để Bessie cố gắng đáp xuống (\(1 \le N \le 1000\)). Mục tiêu \(i\) nằm tại vị trí \(x(i)\) và có giá trị \(p(i)\) điểm nếu Bessie đáp xuống đó. Bessie bắt đầu tại vị trí của bất kỳ mục tiêu nào do cô chọn và chỉ được di chuyển theo một hướng, nhảy từ mục tiêu này sang mục tiêu khác. Mỗi bước nhảy phải dài ít nhất bằng bước nhảy trước đó và phải đáp xuống một mục tiêu.

Bessie nhận được điểm của mọi mục tiêu mà cô chạm vào (bao gồm mục tiêu ban đầu nơi cô xuất phát). Hãy tính tổng điểm lớn nhất cô có thể đạt được.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng \(2..1+N\): dòng \(i+1\) chứa \(x(i)\) và \(p(i)\), mỗi giá trị là một số nguyên trong khoảng \(0..1\,000\,000\).

Dữ liệu ra

• Dòng 1 chứa tổng điểm lớn nhất Bessie có thể nhận được.

Ví dụ

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

25

Nguồn

USACO 2013 November Contest, Silver — Problem 3: Pogo-Cow

Tác giả đề: Brian Dean, 2013.