D2. Magic Powder - 2

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

Input

The first line contains two positive integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 109), 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 b1, b2, ..., bn (1 ≤ bi ≤ 109), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.

Output

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

Examples

input

1 100000000011000000000

output

2000000000

input

10 11000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 10000000001 1 1 1 1 1 1 1 1 1

output

0

input

3 12 1 411 3 16

output

4

input

4 34 3 5 611 12 14 20

output

3

 

题目大意：就是制作一个蛋糕需要n种材料，然后你有k克魔法粉，每克魔法粉可以代替任意一克的材料,ai代表制作一个蛋糕需要第i种材料多少克，bi代表你拥有第i个材料多少克，问做多可以做多少个蛋糕。

题解:二分查找可以制作多少个蛋糕，假如可以制作，那么每一种材料都必须充足。

 

#include
      
       const int maxn= 2 * 1e9 + 2;__int64 n, t, a[100100], b[100100];__int64 f(__int64 z,__int64 y){    __int64 mid, sum;    int i;    while(z<=y)    {        mid=(z+y)/2;        for(sum=0,i=1;i<=n;i++)        {            if(b[i]
       
        t)                break;        }        if(sum==t)            return mid;        else if(sum