e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

III этап Всеукраинской олимпиады по информатике 2011-2012 г. Житомир 1 тур

Новогодние скидки

В течении всех новогодних праздников в компьютерном супермаркете действует акция "Новогодние скидки". Для каждого из N видов товара известны его обычная цена и цена в акции. Какую наибольшую суммарную скидку получим, потратив сумму, не превышающую M, если каждый товар можно приобрести только в единственном экземпляре?

Входные данные

Числа N и M в первой строке, в последующих N строках пары чисел – обычная цена и цена в акции товаров. Все числовые значения натуральные, M1000, другие значения не превышают 100.

Выходные данные

Ответ к задаче.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4 45
14 10
26 20
33 25
20 15
Çıxış verilənləri #1
15

Şərh: Покупаем 1-й, 2-й и 4-й товар, получаем суммарную скидку 15.

Mənbə Stage III All-Ukrainian School Olympiad 2011-2012, Round 1, Zhytomyr