Bò nhảy Pogo

Bessie dùng gậy nhảy pogo để nhảy trên một đường thẳng. Trên đường thẳng có $N$ mục tiêu, mục tiêu thứ $i$ nằm tại vị trí $x_i$ và cho $p_i$ điểm.

Bessie bắt đầu tại một mục tiêu bất kỳ và chỉ di chuyển theo một hướng (sang trái hoặc sang phải). Mỗi bước nhảy phải có khoảng cách ít nhất bằng bước nhảy trước đó (bước nhảy đầu tiên có thể có khoảng cách bất kỳ). Bessie thu được điểm từ tất cả các mục tiêu mà cô đáp xuống (bao gồm cả mục tiêu bắt đầu).

Hãy tìm tổng điểm lớn nhất mà Bessie có thể thu được.

Dữ liệu vào

• Dòng đầu tiên: số nguyên $N$.
• $N$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x_i$ và $p_i$.

Dữ liệu ra

• Một số nguyên duy nhất: tổng điểm lớn nhất.

Ràng buộc

• $1\le N\le 1000$
• $0\le x_i\le {10}^6$
• $1\le p_i\le {10}^6$
• Các vị trí $x_i$ đôi một khác nhau.

Ví dụ