0346. Работа, кофе, профит

Программист Саша очень любит свою работу. Каждый будний день, он просыпается и начинает свой день с кружки горячего молотого кофе, после чего он получает необходимый заряд бодрости, одевает тапочки и идет реализовывать свои идеи в виде кода. Но спустя некоторое время, он опять испытывает необходимость в очередной кружке кофе, чтобы снова приступить к своей работе...

Попробуем математически описать поведение Саши. Проснувшись после длинной (или короткой) ночи, Саша обладает зарядом бодрости Q. Будем считать, что весь рабочий день поделен на N промежутков времени, в каждый из которых он может либо работать, либо пить кофе. Если в i-ый промежуток времени Саша работает, то:

• Саша теряет заряд бодрости q_i (если у Саши было менее q_i единиц бодрости, то его заряд бодрости становится равным нулю);
• завершенность продукта увеличивается на p_i единиц завершенности продукта (PROduct FInishness uniTs, PROFIT);
• если у Саши было меньше q_i единиц бодрости, то следующие K промежутков времени Саша ничего не сможет делать, кроме как пить кофе, общаться с друзьями в социальных сетях или играть в какую-нибудь игру на своей приставке;
• ??????
• PROFIT

Если в i-тый промежуток времени Саша пьёт кофе, то восстанавливает R единиц бодрости. Однако, заряд бодрости Саши не может стать больше чем 100 единиц.

Саша просит Вас узнать, сколько единиц PROFIT он сможет получить за день, если будет действовать оптимальным образом.

Формат входного файла

Первая строка входного файла содержит целые числа Q, N, K, R (0 ≤ Q ≤ 100, 1 ≤ N ≤ 100, 1 ≤ K ≤ N, 1 ≤ R ≤ 100). В следующих N строках содержатся два целых числа q_i, p_i (1 ≤ q_i ≤ 100, 1 ≤ p_i ≤ 10000).

Формат выходного файла

Выведите единственное число – максимальное количество единиц PROFIT, которое может получить Саша.

Пример:

Submit a solution



Printable version