Последний день вашего отпуска, и вы решили купить несколько сувениров, чтобы напоминать себе об этих прекрасных временах. Всего есть $n$ торговцев, и у каждого из них вам приглянулся один товар. Цена товара у $i$-го торговца равна $c_i$. У вас есть $S$ денег, и вы готовы потратить их на сувениры. У вас нет особых предпочтений, поэтому вы просто хотите купить как можно больше различных товаров. Это было бы простой задачей, но речь идет о туристических лавках, которые наживаются на доверчивых туристах.

У $i$-го торговца есть параметр убеждения $p_i$, причем для всех торговцев эти параметры различны. Чем больше сувениров вы уже купили, тем больше торговец уверен в вашей готовности тратить деньги на всякую ерунду. Если торговец видит, что вы уже купили $k$ сувениров, он повышает цену на свой товар до $c_i + k \cdot p_i$.

Какое максимальное количество сувениров вы можете купить?

Входные данные

Первая строка содержит два целых числа $n$ и $S$ ($1 \le n \le 10^5$, $0 \le S \le 10^9$) — количество торговцев и количество денег, которые у вас есть.

Вторая строка содержит $n$ целых чисел $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — начальные цены всех сувениров.

Третья строка содержит $n$ целых чисел $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — параметры убеждения всех торговцев. Гарантируется, что они различны.

Выходные данные

Выведите одно число — сколько сувениров вы можете купить.

Примеры

Входные данные 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