Age of Empires
(Время: 2 сек. Память: 32 Мб Сложность: 54%)
Представьте себе стратегическую компьютерную игру «Age of Empires», в которой вы управляете империей, включающей в себя территорию определенной площади и армию. Вам необходимо поддерживать стабильность империи, которая выражается целым числом от 1 до 100. Если стабильность в определенный момент становится ниже единицы, то происходит крушение империи и игра заканчивается. В начале игры стабильность равна 100.
Каждый игровой год Вам предлагается для присоединения одна из соседних территорий, и Вы должны выбрать: присоединять или не присоединять эту территорию. В случае присоединения стабильность снижается на некоторую величину Fi, а размер империи увеличивается на размер присоединяемой территории Ti. В начале игры Вы имеете нулевой размер территории империи. Если Вы не присоединяете территорию, то стабильность возрастает на значение P. При этом если сумма становится больше 100, то она уменьшается до 100.
Определите значение максимально возможного размера империи, который может быть у Вас к концу игры при условии, что в процессе игры не было крушения империи.
Входные данные
В первой строке входного файла INPUT.TXT содержатся два целых числа: продолжительность партии в годах N (1 ≤ N ≤ 104) и скорость стабилизации в годы без присоединений P (0 ≤ P ≤ 99).
Далее следует N строк, каждая из которых содержит два целых числа: i-я строка описывает территорию, возможную для присоединения в i-й год: величину уменьшения стабильности при присоединении Fi (1 ≤ Fi ≤ 99) и размер территории Ti (1 ≤ Ti ≤ 105).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 15
40 1900
92 4740
70 3200 | 5100 |
Пояснение к примеру
Здесь нужно присоединить первую и третью территории. В первый год стабильность после присоединения снизится до 60, во второй год возрастет до 75, в третий снова снизится до 5.
Система оценки
Решения, работающие только для P = 0 и Fi = 99 и для теста из условия, будут оцениваться в 25 баллов.
Решения, работающие только для P = 99 и Fi = 99 и для теста из условия, будут оцениваться в 30 баллов.
Решения, работающие только для P = 0 и для теста из условия, будут оцениваться в 50 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
