Впродовж усіх новорічних свят у комп’ютерному супермаркеті діє акція "Новорічні знижки". Для кожного з N
видів товару відомо його звичайну та акційну ціну. Яку найбільшу сумарну знижку отримаємо, витративши суму, що не перевищує M
, якщо кожен товар можна придбати тільки в єдиному екземплярі?
Числа N
і M
у першому рядку, у наступних N
рядках пари чисел – звичайна та акційна ціна товарів. Усі числові значення натуральні, M ≤ 1000
, інші значення не перевищують 100.
Відповідь до задачі.