FJ занялся продажей безделушек, покупая и продавая, например, украшения рождественской ёлки в виде коров. Он знает, что продаст каждую закупленную вещицу из каталога $N$ ($1 \le N \le 100$) видов коровьих сувениров, и может купить сколько угодно каждого вида. У него лишь $M$ ($1 \le M \le 100,000$) денег для вложения, но он хочет максимизировать прибыль (определённую несколько необычно) к концу первого года работы.

Вещица вида $i$ стоит $C_i$ ($1 \le C_i \le 100,000$), а её продажа приносит $R_i$ ($1 \le R_i \le 100,000$) дохода за штуку (прибыль $R_i-C_i$). FJ может как угодно сочетать виды продаваемых вещей. При закупке необязательно тратить все деньги.

Какова максимальная общая прибыль ($profit = initial\_cash - all\_costs + all\_sales$) в конце первого года? Гарантируется, что она меньше $1,000,000,000$.

Рассмотрим лишь $3$ вида вещей и начальную сумму $M=17$. Стоимости и доходы каждого вида указаны ниже:

             Сувенир     Стоимость     Доход
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

Здесь FJ следует купить $5$ вещей вида $3$ за $15$ и ещё $1$ вещь вида $1$ за $2$, всего за $17$. Прибыль составит $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$. При таких стоимостях и доходах большего получить нельзя.

Примечание: второй тест сложен, но наш ответ верен.

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

• Строка 1: два целых числа, разделённых пробелом: $N$ и $M$.

• Строки $2..N+1$: строка $i+1$ содержит два целых числа, разделённых пробелом: $C_i$ и $R_i$.

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

• Строка 1: максимальная прибыль FJ при заданных стоимостях и доходах.

Примеры

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

3 17
2 4
5 6
3 7

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

22

Источник задачи: традиционная задача, 2009.