Для ускорения своей призовой коровы Беси, Фермер Джон имеет палку для каждой из ног Беси. Теперь Беси научилась ускоряться, но еще не научилась замедляться.
Для тренировки ФД разметил путь по прямой. В различных позициях этого пути он разместил N целей, в которых Беси должна приземляться (1 <= N <= 1000). Цель I расположена в позиции x(i) и имеет цену P(i) очков, которые получит Беси, если приземлится в этой точке.
Беси начинает прыжки из любой из этих целей по своему выбору, и ей разрешено двигаться только в одном направлении, прыгая от цели к цели. Каждый прыжок должен быть по расстоянию не меньше, чем предыдущий, и приземляться в целевой точке. Беси получает соответствующие очки за каждую цель, которой коснётся, включая ту, с которой начнёт. Определите максимальное количество очков, которое она может получить. PROBLEM NAME: pogocow
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит x(i) и p(i), целые в диапазоне 0..1,000,000.
Формат выходных данных
* Строка 1: Максимальное количество очков, которое может получить Беси.
Примечание
Беси прыгает из позиции x=4 (8 очков) в позицию 5 (6 очков), в позицию 7 (6 очков), в позицию 10(5 очков).