Задачи с дедлайнами: максимальная выручка

Фрилансер получил n заказов. Каждый заказ занимает ровно один день, у заказа i есть дедлайн dᵢ (его нужно выполнить в один из дней 1 … dᵢ) и оплата pᵢ. В день можно выполнить только один заказ, работа начинается с дня 1. Какую максимальную сумму можно заработать?

Ввод: в первой строке n (1 ≤ n ≤ 2500), далее n строк d p (1 ≤ d ≤ 10⁹, 1 ≤ p ≤ 10⁹).

Вывод: максимальная выручка (может не поместиться в 32 бита).

Пример 1

Ввод:

4
2 100
1 19
2 27
1 25

Вывод:

127

Пример 2

Ввод:

3
1 5
1 7
1 6

Вывод:

7