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$）。売る小物を自由に組み合わせられます。購入時に全資金を使う必要はありません。

最初の年の終わりに得られる総利益（$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

この場合、種類 $3$ を $5$ 個、$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 年。