Problems
Новогодние скидки
Новогодние скидки
В течении всех новогодних праздников в компьютерном супермаркете действует акция "Новогодние скидки". Для каждого из N видов товара известны его обычная цена и цена в акции. Какую наибольшую суммарную скидку получим, потратив сумму, не превышающую M, если каждый товар можно приобрести только в единственном экземпляре?
Входные данные
Числа N и M в первой строке, в последующих N строках пары чисел – обычная цена и цена в акции товаров. Все числовые значения натуральные, M ≤ 1000, другие значения не превышают 100.
Выходные данные
Ответ к задаче.
Input example #1
4 45 14 10 26 20 33 25 20 15
Output example #1
15
Example description: Покупаем 1-й, 2-й и 4-й товар, получаем суммарную скидку 15.