F. Восхождение на пик Ленина

Альпинист Темир собирается покорить пик Ленина (7134 м) — высочайший пик Памира на территории Кыргызстана. Восхождение запланировано на N дней. К началу первого дня запас энергии Темира равен E.

Каждый день Темир выбирает: идти или отдыхать.

• Если он идёт в день i — поднимается на h_i метров и тратит e_i единиц энергии.
• Если отдыхает — высота не меняется, энергия не тратится (но и не восстанавливается).

Энергия Темира не должна становиться отрицательной ни в один момент.

Темир сам решает, в какие дни идти, в какие отдыхать. На какую максимальную высоту он сможет подняться к концу N-го дня?

Входные данные

• Первая строка: два числа N и E (1 ≤ N ≤ 500, 1 ≤ E ≤ 5000).
• Далее N строк: два целых числа h_i и e_i (1 ≤ h_i ≤ 10⁴, 0 ≤ e_i ≤ E) — прирост высоты и затраты энергии в день i.

Выходные данные

Одно целое число: максимальная высота, которой можно достичь.

Пример 1

Вход:

3 5
3 2
4 3
5 5

Выход:

7

Пример 2

Вход:

4 10
6 4
5 3
4 2
3 1

Выход:

18

Пример 3

Вход:

1 1
100 5

Выход:

0

Пояснение

В первом примере: идём дни 1 и 2 (высота 3+4=7, энергия 2+3=5 ≤ 5), день 3 пропускаем. Во втором: всех 4 дня хватает энергии (4+3+2+1=10), общая высота 6+5+4+3=18. В третьем — энергии 1, а на восхождение нужно 5, остаёмся внизу.

Подсказка по алгоритму: замаскированный 0/1 рюкзак. Динамика по таблице dp[использованная_энергия]. Сложность O(N·E), проходит для всех 5 языков.