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 可以任意搭配出售的擺件。購買時不必花光全部資金。

FJ 在營業第一年結束時能獲得的最大總利潤（$profit = initial\_cash - all\_costs + all\_sales$）是多少？保證這個數小於 $1,000,000,000$。

考慮 FJ 只有 $3$ 種擺件、初始資金為 $M=17$ 的情況。各擺件的成本和收入如下：

             擺件     成本     收入
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

此時 FJ 應花 $15$ 購買 $5$ 件第 $3$ 種擺件，再花 $2$ 購買 $1$ 件第 $1$ 種擺件，共花 $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 年。