Ограничения: время – 200ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В пошаговой стратегической игре "Age of Empires" (Эпоха империй) игрок управляет растущей Римской империей. Игрок должен
поддерживать стабильность империи, которая должна находиться в диапазоне от 1 до 100. Если стабильность падает
до 0 или ниже -- игрок проигрывает. В начале игры стабильность равна 100. Каждый год игроку предлагается для присоединения одна
из соседних территорий, и игрок должен выбрать: присоединять или не присоединять эту территорию. При присоединении стабильность
снижается на некоторую величину `F_i` в зависимости текущей ситуации на этой территории, а размер империи увеличивается на размер территории `T_i`.
В начале игры размер империи равен 0. Если игрок выбирает не присоединять территорию, то стабильность империи возрастает на `P` единиц, но при
этом стабильность не может превысить 100 (если сумма становится больше 100, она уменьшается до 100).
Определите, какой максимальный размер империи может быть у игрока к концу партии, без крушения его империи.
В первой строке ввода содержатся два целых числа: продолжительность партии в годах `N` (`1 <= N <= 10000`) и скорость стабилизации
в годы без присоединений `P` (`0 <= P <= 99`). Далее следует `N` строк, каждая из которых содержит
два целых числа: `i`-я строка описывает территорию, возможную для присоединения в `i`-й год: величину уменьшения стабильности
при присоединении `F_i` (`1 <= F_i <= 99`) и размер территории `T_i` (`1 <= T_i <= 100000`).
Выведите одно целое число -- максимальный размер империи через `N` лет.
```sample Пример ввода
3 15
60 1800
90 5000
50 3300
```
```sample Пример вывода
5100
```
Пояснение к примеру: можно присоединить первую и третью территории.
В первый год стабильность после присоединения снизится до 40, во второй год возрастет до 55, в третий
снова снизится до 5.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (20 баллов)||
`P = 0`, `F_i = 99`, остальные ограничения из условий задачи
||.u|Подзадача 2 (20 баллов)||
`P = 99`, `F_i = 99`, остальные ограничения из условий задачи
||.u|Подзадача 3 (30 баллов)||
`P = 0`, остальные ограничения из условий задачи
Необходимые подзадачи: 1, 2.
||.u|Подзадача 4 (30 баллов)||
Ограничения из условий задачи.
Необходимые подзадачи: 1, 2, 3.
Баллы за каждую из подзадач начисляются только в случае,
если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат о первой ошибке.
Хотя пример ввода не соответствует ограничениям подзадач 1, 2 и 3, ваше решение должно давать правильный ответ и на этом
примере для выполнения дальнейшего тестирования.
Начало
Рабочее место участника
Динамическое программирование и запоминающие функции