D. Грабли

Петя приехал на дачу к своему деду. Дедушка в молодости воевал, потому очень ответственно подошёл к защите своей дачи от нежелательных посетителей. Во-первых, тропинка к дому засажена по обе стороны особо колючими кустами, поэтому свернуть с неё никак не получится. А во-вторых, на тропинке разложены N различных видов замаскированных грабель в расчёте на то, что незваные гости будут наступать на них и получать этими самыми граблями по лбу.

Петя помнит, что грабель i-го вида у деда имеется b_i штук. Если наступить на грабли i-го вида a_i раз, то можно наконец получить необходмый опыт для преодоления таких грабель в следующий раз и более ни разу ими по лбу не получать. Помимо этого Петя умеет перепрыгивать грабли, но может это сделать не более чем K раз. При этом перепрыгивание грабель хоть и позволяет избежать удара по лбу, но не даёт опыта в обхождении таких грабель. Следовательно, чтобы научиться обходить грабли i-го вида, Пете придётся обязательно получить такими граблями a_i раз по лбу.

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

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

В первой строке входного файла находятся два числа N и K – количество видов грабель, разложенных заботливым дедом и количество прыжков, которое может совершить Петя (1 ≤ N ≤ 10⁴, 1 ≤ K ≤ 10³).

Далее следует N строк, по два числа в каждой – a_i и b_i, количество раз, которое требуется получить граблями i-го вида по лбу, чтобы научиться их обходить и количество грабель i-го вида, лежащих на пути до дачи (1 ≤ a_i ≤ b_i ≤ 10³).

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

Выведите единственное число – минимально возможное количество ударов по лбу, которое получит Петя, добравшись до дачного домика.

Пример:

В первом примере Пете нужно перепрыгнуть все грабли первого вида, потратив при этом все прыжки. После этого он один раз получит по лбу граблями второго вида, в результате чего научится их обходить и минует все оставшиеся грабли.

Во втором примере Петя в любом случае получит пять раз по лбу граблями каждого вида, поскольку даже если он перепрыгнет грабли какого-нибудь вида три раза, после этого он всё равно из оставшихся семи грабель такого вида пятью получит по лбу (и только потом научится эти грабли обходить).

Если Ваше решение работает для случая a_i = 1, оно будет оцениваться из 40 баллов. Не забудьте в таком случае добавить в программу заглушки для тестов из условия, чтобы программа была принята тестирующей системой на проверку.

Источник: XXIV Городская олимпиада школьников по информатике

Обсудить       Отправить решение



Версия для печати