这个问题的术语与上一个问题相同,唯一的例外是增加限制。
输入
第一行包含两个正整数n和k(1≤n≤100000,1≤k≤109)——魔粉的成分数和克数。
第二行包含序列 a1, a2, ..., an (1 ≤ ai ≤ 109),其中第 i 个数字等于烘焙一块饼干所需的第 i 个成分的克数。
第三行包含序列 b1, b2, ..., bn (1 ≤ bi ≤ 109),其中第 i 个数字等于 Apollinaria 拥有的第 i 个成分的克数。
输出
打印阿波利纳里亚使用她拥有的原料和魔法粉能够烘烤的饼干的最大数量。
示例
输入 #1
1 1000000000 1 1000000000
输出 #1
2000000000
输入 #2
10 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1 1 1 1 1 1 1 1 1 1
输出 #2
0
输入 #3
3 1 2 1 4 11 3 16
输出 #3
4
输入#4
4 3 4 3 5 6 11 12 14 20
输出#4
3