Doka Eating

問題文

高橋君はドカ食いが大好きなので、ドカ食いをするためにハンバーガー屋に入りました。

このハンバーガー屋には $N$ 種類のハンバーガーが販売されており、各ハンバーガーには $1, 2, ... ,N$ の番号が振られています。

各 $i \ (1 \leq i \leq N)$ について、ハンバーガー $i$ の値段は $C_i$ 円、重さは $W_i$ グラムであり、すべて在庫は ${100}^{{100}^{100}}$ 個ずつあります。

高橋君が持っている金額 $M$ 円が与えられるので、高橋君が購入できるハンバーガーの総重量の最大グラム数を求めてください。

制約

• $1 \leq N, M \leq 10^{5}$
• $1 \leq C_i, W_i \leq 10^{5}$
• $(C_1, W_1) = (1, 100)$
• 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

5 8
1 100
2 400
2 500
1 200
3 800

2100

ハンバーガー $3$ を $1$ 個、ハンバーガー $5$ を $2$ 個注文する場合、値段の合計は $2 + 3 \times 2 = 8$ 円、重さの合計は $500 + 800 \times 2= 2100$ グラムとなります。

値段の合計が $8$ 円以下の注文方法で、総重量が $2100$ グラムを超えるものは存在しないため、答えは $2100$ となります。

7 5
1 100
1 100
1 121
1 144
1 169
2 169
3 169

845

異なる種類のハンバーガーでも、同じ値段や同じ重さのものが存在する場合もあります。

11 9364
1 100
85 8101
69 9579
29 6871
33 9326
83 4236
64 7272
73 8709
10 6855
85 2435
36 9773

6416680

2 100000
1 100
100000 100000

10000000