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

Эта задача предлагается в двух вариантах, которые отличаются только ограничениями. Если вы можете решить эту задачу в больших ограничениях, то вы можете сразу написать одно решение на оба варианта. Если же решение в больших ограничениях вызывает затруднение, вы можете решить только упрощённый вариант.

Проснувшись с утра, Аполлинария решила испечь печенек. Для того чтобы испечь одну печеньку, нужно $$$n$$$ ингредиентов, причем про каждый ингредиент известно число $$$a_i$$$ — сколько грамм этого ингредиента необходимо для того, чтобы испечь одну печеньку. Для приготовления одной печеньки необходимо использовать все $$$n$$$ ингредиентов в нужных пропорциях.

У Аполлинарии есть $$$b_i$$$ грамм $$$i$$$-го ингридиента. Кроме того, у неё есть $$$k$$$ грамм волшебного порошка. Каждый грамм волшебного порошка можно превратить ровно в $$$1$$$ грамм любого из $$$n$$$ ингредиентов и использовать для приготовления печенек.

Перед вами стоит задача — определить максимальное количество печенек, которое сможет испечь Аполлинария при помощи имеющихся у неё ингредиентов и волшебного порошка.

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

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

Во второй строке следует последовательность $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$i$$$-е число равно количеству грамм $$$i$$$-го ингредиента, необходимых для приготовления одной печеньки.

В третьей строке следует последовательность $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$), где $$$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
Примечание

Первые два примера обращают внимание на более высокие ограничения в сложной версии задачи.

В третьем примере Аполлинарии выгодно превратить $$$1$$$ имеющийся у неё грамм волшебного порошка в ингредиент номер $$$2$$$, тогда она сможет испечь $$$4$$$ печеньки.

Во четвертом примере Аполлинарии выгодно превратить $$$1$$$ грамм волшебного порошка в ингредиент номер $$$1$$$ и $$$1$$$ грамм волшебного порошка в ингредиент номер $$$3$$$. Тогда она сможет испечь $$$3$$$ печеньки. Оставшийся $$$1$$$ грамм волшебного порошка можно оставить, так как с помощью него ответ увеличить невозможно.