Magic Powder - 2

题意翻译

给你N种材料，以及M个魔法材料。 每个魔法材料可以变成任意一种魔法材料。 现在已知做一个饼干要用每种材料Ai个，而且已知每种饼干我们初始有Bi个。 问最多可以做出来多少饼干。

题目描述

The term of this problem is the same as the previous one, the only exception — increased restrictions.

输入输出格式

输入格式

The first line contains two positive integers $ n $ and $ k $ ( $ 1<=n<=100000,1<=k<=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},...,a_{n} $ ( $ 1<=a_{i}<=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},...,b_{n} $ ( $ 1<=b_{i}<=10^{9} $ ), where the $ i $ -th number is equal to the number of grams of the $ i $ -th ingredient, which Apollinaria has.

输出格式

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

输入输出样例

输入样例 #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