CF670D2 Magic Powder - 2

本题与前一题的题意相同，唯一的区别是限制条件更加严格。

第一行包含两个正整数 $n$ 和 $k$（$1 \leq n \leq 100000, 1 \leq k \leq 10^{9}$），分别表示原料的种类数和魔法粉的克数。 第二行包含序列 $a_{1}, a_{2}, ..., a_{n}$（$1 \leq a_{i} \leq 10^{9}$），其中第 $i$ 种原料制作一个饼干所需的克数。 第三行包含序列 $b_{1}, b_{2}, ..., b_{n}$（$1 \leq b_{i} \leq 10^{9}$），其中 $b_{i}$ 表示 Apollinaria 拥有的第 $i$ 种原料的克数。

输出 Apollinaria 能够利用现有原料和魔法粉制作的最大饼干数。

由 ChatGPT 4.1 翻译