問題文

無限に続く数直線上でスライムのレースが行われていて、$N$ 匹のスライムが参加しています。
$i$ 番目のスライムは時刻 $0$ に座標 $x_i$ に居て、 正の方向に一定の速さ $v_i$ で進んでいます。

レースは１本の直線上で行われているので、 レース中にスライムたちが衝突することがあります。
ある時刻 $t$ に複数のスライムが同一の座標にいる状態になったとき、 それらのスライムは以下のように変化します。

・番号の一番小さいスライムがその他のスライムを全て吸収し、吸収されたスライムは消滅する。
　番号の一番小さいスライムは、速さが
　（自分の吸収前の速さ）＋（自分が吸収したスライムの速さの和）
　に変化する。

さて、全てのスライムについて時刻 $0$ から時刻 $t$ までに走った距離を求め、 それらを足し合わせた総和を $f(t)$ と表します。

$f(T)\ge D$ である最小の整数 $T$ を求めてください。

なお、吸収され消滅したスライムは、その時点で走るのを終了したとみなして下さい。

入力

$ND$
$x_1\cdots x_N$
$v_1\cdots v_N$

【制約】
・$1\le N\le {10}^5$
・$1\le D\le {10}^9$
・$1\le x_i\le {10}^9$
・$1\le v_i\le {10}^9$
・$i<j$ ならば $x_i<x_j$
・入力は全て整数である。

出力

問題文の条件を満たす整数 $T$ を出力せよ。

サンプル

3 40
2 5 100
6 4 5

3

3 9
1 3 7
1 1 1

3

1 160
314
159

2