Сьогодні останній день вашої відпустки, і ви вирішили купити сувеніри на згадку про ці приємні часи. Є $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, \ldots, c_n$ ($1 \le c_i \le 10^9$) — початкові ціни всіх сувенірів.

Третій рядок містить $n$ цілих чисел $p_1, p_2, \ldots, 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