休暇の最終日、あなたは楽しい思い出を振り返るための記念品をいくつか買うことにしました。$n$ 人の商人がいて、それぞれの商人から商品を 1 つずつ気に入りました。$i$ 番目の商人の商品に書かれている価格は $c_i$ です。あなたは $S$ のお金を持っており、それをすべて記念品に使うつもりです。特にこだわりはないため、できるだけ多くの異なる商品を買いたいと考えています。本来なら簡単なことですが、ここは観光地のお土産屋です。彼らは騙されやすい観光客を相手に商売をしています。

$i$ 番目の商人には説得パラメータ $p_i$ があり、これは商人ごとに異なります。あなたがすでに持っている記念品の数が多いほど、商人はあなたが無価値なガラクタにお金を使う意志があると確信します。もし商人があなたがすでに $k$ 個の記念品を買ったことを知ると、彼らは自分の商品の価格を $c_i + k \cdot p_i$ に引き上げます。

あなたが買うことができる記念品の最大数はいくつでしょうか。

入力

入力は以下の形式で与えられます。

$n$ $S$ $c_1$ $c_2, \dots, c_n$ $p_1, p_2, \dots, p_n$

• $1 \le n \le 10^5$
• $0 \le S \le 10^9$
• $1 \le c_i \le 10^9$
• $0 \le p_i \le 10^9$
• $p_i$ はすべて異なることが保証されている。

出力

買うことができる記念品の最大数を 1 つの数値で出力してください。

入出力例

入力 1

2 5
1 1
10 11

出力 1

1

入力 2

2 22
10 1
0 10000

出力 2

2

入力 3

1 0
1
0

出力 3

0