Эта задача предлагается в двух вариантах, которые отличаются только ограничениями. Если вы можете решить эту задачу в больших ограничениях, то вы можете сразу написать одно решение на оба варианта. Если же решение в больших ограничениях вызывает затруднение, вы можете решить только упрощённый вариант.
Проснувшись с утра, Аполлинария решила испечь печенек. Для того чтобы испечь одну печеньку, нужно $$$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$$$ грамм волшебного порошка можно оставить, так как с помощью него ответ увеличить невозможно.
| Codeforces Round 350 (Div. 2) |
|---|
| Закончено |
