Петя, старший брат Васи, очень любит играть в компьютерные игры. В одной из своих любимых игр Петя дошел до последнего уровня, на котором происходит битва с боссом.
Во время прохождения игры Петя находил свитки с заклинаниями, и теперь ему предстоит их использовать. Опишем, как происходит бой на этом уровне:
1) У босса есть два параметра max — начальное количество здоровья, и reg — ежесекундная регенерация.
2) У каждого свитка также есть два параметра: powi — сила заклинания, измеряемая в процентах — максимальное количество здоровья босса, отсчитываемое от исходного, при котором можно использовать данный свиток (т. е. если у босса больше powi процентов здоровья, свиток применять нельзя); и dmgi — урон в секунду, который получает босс, если использовать этот свиток. Как только какой-то свиток использован, он пропадает, и на босса накладывается еще одно заклинание, которое будет наносить ему dmgi урона каждую секунду до конца игры.
Действия в бою в течение одной секунды, происходят в следующем порядке: сначала босс получает урон от всех заклинаний, наложенных на него, затем восстанавливает reg здоровья (при этом, больше чем max здоровья получиться не может), а затем игрок может использовать очередной свиток (не больше одного в секунду).
Босс считается поверженным, если в конце какой-то секунды количество здоровья стало неположительным ( ≤ 0).
Помогите Пете определить, может ли он выиграть с имеющимся набором свитков, и если может, то за какое минимальное количество секунд он сможет это сделать.
В первой строке записаны три целых числа N, max и reg (1 ≤ N, max, reg ≤ 1000) — количество свитков, и параметры босса. В следующих N строках записаны по два целых числа powi и dmgi — параметры i-го свитка (0 ≤ powi ≤ 100, 1 ≤ dmgi ≤ 2000).
В случае если Петя не сможет пройти этот уровень, в единственной строке выведите NO.
Иначе в первой строке выведите YES. Во второй строке выведите минимальное время, через которое босс может быть повержен и количество использованных свитков. В следующих строках для каждого использованного свитка выведите через пробел количество секунд, прошедших с начала боя, до его использования и номер использованного свитка. Свитки нумеруются с 1 в том порядке, в котором они заданы во входных данных. Считается, что первый свиток можно использовать через 0 секунд.
Свитки выводите в том порядке, в котором их нужно использовать. Запрещается использовать свитки после того как босс повержен.
2 10 3
100 3
99 1
NO
2 100 10
100 11
90 9
YES
19 2
0 1
10 2
| Codeforces Beta Round 37 |
|---|
| Закончено |
