D2. Волшебный порошок - 2
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Условие этой задачи полностью совпадает с предыдущей, единственное исключение — повышенные ограничения.

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

В первой строке входных данных следуют два целых положительных числа n и k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109) — количество ингредиентов и количество грамм волшебного порошка.

Во второй строке следует последовательность a1, a2, ..., an (1 ≤ ai ≤ 109), где i-е число равно количеству грамм i-го ингредиента, необходимых для приготовления одной печеньки.

В третьей строке следует последовательность b1, b2, ..., bn (1 ≤ bi ≤ 109), где i-е число равно количеству грамм i-го ингредиента, которые есть у Аполлинарии.

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

Выведите целое число — максимальное количество печенек, которые сможет испечь Аполлинария при помощи волшебного порошка.

Примеры
Входные данные
1 1000000000
1
1000000000
Выходные данные
2000000000
Входные данные
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1
Выходные данные
0
Входные данные
3 1
2 1 4
11 3 16
Выходные данные
4
Входные данные
4 3
4 3 5 6
11 12 14 20
Выходные данные
3