To ostatni dzień twoich wakacji i postanowiłeś kupić kilka pamiątek, aby przypominały ci o tych miłych chwilach. Jest $n$ sprzedawców, a u każdego z nich upodobałeś sobie jeden przedmiot. Cena przedmiotu u $i$-tego sprzedawcy wynosi $c_i$. Masz przy sobie $S$ pieniędzy i jesteś gotów wydać je na pamiątki. Nie masz żadnych preferencji, więc po prostu chcesz kupić jak najwięcej różnych przedmiotów. Byłoby to łatwe zadanie, ale mówimy tu o sklepach turystycznych, które żerują na łatwowiernych turystach.

$i$-ty sprzedawca posiada parametr perswazji $p_i$, przy czym wartości te są różne dla każdego sprzedawcy. Im więcej pamiątek już posiadasz, tym bardziej sprzedawca jest przekonany o twojej chęci wydawania pieniędzy na bezwartościowe drobiazgi. Jeśli sprzedawca widzi, że kupiłeś już $k$ pamiątek, podnosi cenę swojego przedmiotu do $c_i + k \cdot p_i$.

Jaka jest maksymalna liczba pamiątek, które możesz kupić?

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $S$ ($1 \le n \le 10^5$, $0 \le S \le 10^9$) — liczbę sprzedawców oraz ilość posiadanych pieniędzy.

Druga linia zawiera $n$ liczb całkowitych $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — początkowe ceny wszystkich pamiątek.

Trzecia linia zawiera $n$ liczb całkowitych $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — parametry perswazji wszystkich sprzedawców. Gwarantuje się, że są one parami różne.

Wyjście

Wypisz jedną liczbę — ile pamiątek możesz kupić.

Przykład

Wejście 1

2 5
1 1
10 11

Wyjście 1

1

Wejście 2

2 22
10 1
0 10000

Wyjście 2

2

Wejście 3

1 0
1
0

Wyjście 3

0