2191: Роботопес
Перегляд у форматі PDFКомпанія DOG International розробила унікального робота-пса із не менш унікальним інтелектом. Робот швидко бігає і при цьому може робити стрибки якої завгодно довжини. Для того, щоб продемонструвати можливості нового робота, розробники поставили науковий експеримент. Робот має рухатися по розміченій прямій. В різних позиціях на прямій знаходиться ~N~ цілей, в яких робот має приземлитися після чергового стрибка(під час експерименту робот буде лише стрибати). Ціль ~i~ розташована у позиції ~x_i~ та має ціну ~p_i~ балів, які зарахуються в актив робота після приземлення у цій позиції.
Робот може почати свій рух із будь-якої позиції, і йому дозволяється рухатися лише в одному напрямку стрибаючи від однієї цілі до іншої. При цьому, кожен наступний стрибок повинен бути зроблений на відстань не меншу за попередню, і приземлятися він має лише у цільових точках. За кожну цільову точку робот отримує відповідні бали включаючи початкову точку.
Яку максимальну кількість балів повинен отримати робот на цих випробуваннях.
Input
Перший рядок містить ціле число ~N~ (~1 \le N \le 1000~) - кількість цільових точок.
Наступні ~N~ рядків містять координату позиції ~x_i~ (~0 \le x_i \le 10^6~) та її ціну ~p_i~ (~0 \le p_i \le 10^6~).
Output
Виведіть максимальну кількість балів, які теоретично можна набрати у таких випробуваннях.
Sample Input 1
6
5 6
1 1
10 5
7 6
4 8
8 10
Sample Output 1
25
Notes
Перший стрибок треба зробити з позиції x = 4 (8 балів) в позицію 5 (6 балів), далі на ціль 7 (6 балів) і в точку 10 (5 балів)
Коментарі
Гарантується що усі X різні?
без відповіді - читаємо умову