Восхождение на пик Ленина
Альпинист планирует тренировочные подъёмы в течение N дней. В день i он может один раз подняться на hᵢ метров, затратив eᵢ единиц энергии, или пропустить подъём. Начальный запас энергии равен E; отдых его не восстанавливает. Выберите дни так, чтобы суммарные затраты не превышали E, а суммарный набор высоты был наибольшим. Набор высоты считается от нуля и не ограничивается высотой какой-либо вершины. Подъём с нулевыми затратами тоже можно выполнить лишь один раз.
Входные данные
В первой строке даны N и E (1 ≤ N ≤ 500, 1 ≤ E ≤ 5000). В каждой из следующих N строк даны целые hᵢ и eᵢ (1 ≤ hᵢ ≤ 10000, 0 ≤ eᵢ ≤ 10000). Затраты отдельного подъёма могут превышать весь запас E — такой подъём выполнить нельзя.
Выходные данные
Выведите максимальный суммарный набор высоты. Если нельзя выполнить ни одного подъёма, выведите 0.
Пример
Ввод
3 5
3 2
4 3
5 5
Вывод
7
Комментарии