CF670D2.Magic Powder - 2

This problem is given in two versions that differ only by constraints. If you can solve this problem in large constraints, then you can just write a single solution to the both versions. If you find the problem too difficult in large constraints, you can write solution to the simplified version only.

Waking up in the morning, Apollinaria decided to bake cookies. To bake one cookie, she needs $n$ ingredients, and for each ingredient she knows the value $a_i$ — how many grams of this ingredient one needs to bake a cookie. To prepare one cookie Apollinaria needs to use all $n$ ingredients.

Apollinaria has $b_i$ gram of the $i$-th ingredient. Also she has $k$ grams of a magic powder. Each gram of magic powder can be turned to exactly $1$ gram of any of the $n$ ingredients and can be used for baking cookies.

Your task is to determine the maximum number of cookies, which Apollinaria is able to bake using the ingredients that she has and the magic powder.

本题提供两个版本，二者仅约束条件不同。若你能在大约束条件下解决本题，则只需编写一个适用于两个版本的统一解法；若你觉得大约束条件下的版本过于困难，也可仅编写简化版本的解法。

清晨醒来后，阿波利纳里亚决定烤饼干。制作一块饼干需要 $n$ 种原料，对于第 $i$ 种原料，她已知其用量 $a_i$（单位：克），即每块饼干所需该原料的克数。制作一块饼干必须使用全部 $n$ 种原料。

阿波利纳里亚目前拥有第 $i$ 种原料 $b_i$ 克。此外，她还拥有 $k$ 克魔法粉末。每克魔法粉末可精确转化为任意一种原料的 $1$ 克，并可用于烤制饼干。

你的任务是：在充分利用现有原料和魔法粉末的前提下，计算阿波利纳里亚最多能烤制多少块饼干。

The first line contains two positive integers $n$ and $k$ ($1 \le n \le 100\,000, 1 \le k \le 10^9$) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where the $i$-th number is equal to the number of grams of the $i$-th ingredient, needed to bake one cookie.

The third line contains the sequence $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$), where the $i$-th number is equal to the number of grams of the $i$-th ingredient, which Apollinaria has.

第一行包含两个正整数 $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$ 种食材的克数。

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.

输出阿波利纳里亚利用现有食材和魔法粉末最多能制作的饼干数量。

The first two examples highlight the larger constraints of the input in this version.

In the third example, it is profitably for Apollinaria to make the existing $1$ gram of her magic powder to ingredient with the index $2$, then Apollinaria will be able to bake $4$ cookies.

In the fourth example, Apollinaria should turn $1$ gram of magic powder to ingredient with the index $1$ and $1$ gram of magic powder to ingredient with the index $3$. Then Apollinaria will be able to bake $3$ cookies. The remaining $1$ gram of the magic powder can be left, because it can't be used to increase the answer.

前两个示例突出了本版本中输入更大的约束条件。

在第三个示例中，阿波利纳里娅将现有的 $1$ 克魔法粉末转化为索引为 $2$ 的原料是最优策略，这样阿波利纳里娅便能烘烤出 $4$ 块饼干。

在第四个示例中，阿波利纳里娅应将 $1$ 克魔法粉末转化为索引为 $1$ 的原料，再将 $1$ 克魔法粉末转化为索引为 $3$ 的原料。这样阿波利纳里娅便能烘烤出 $3$ 块饼干。剩余的 $1$ 克魔法粉末可以保留，因为它无法用于进一步提升答案。