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

Вхідні дані

Числа N і M у першому рядку, у наступних N рядках пари чисел – звичайна та акційна ціна товарів. Усі числові значення натуральні, M ≤ 1000, інші значення не перевищують 100.

Вихідні дані

Відповідь до задачі.