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


Отправить решение Решать в редакторе

Сложность: 32%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Альпинист планирует тренировочные подъёмы в течение 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

Комментарии

Еще нет ни одного комментария.