Magic Powder - 2

https://codeforces.com/contest/670/problem/D2

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 1000000000
1
1000000000

output

2000000000

input

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1

output

0

input

3 1
2 1 4
11 3 16

output

4

input

4 3
4 3 5 6
11 12 14 20

output

3

题意：同上一题，就是数开大了，得用二分 Hait: INF比较小，所以得用3000000000ll就行了

#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef  long long ll ;
ll need[100008];
ll have[100008];
ll tmpp[100008];
ll n,k;
ll Slove(ll mid)
{   ll sum=k;
    for(ll i=1;i<=n;i++)
    {
        tmpp[i]=have[i]-mid*need[i];
        if(tmpp[i]<0)sum+=tmpp[i];
        if(sum<0)return 0;
    }
    return 1;
}
int main()
{
    while(~scanf("%I64d%I64d",&n,&k))
    {
        for(ll i=1;i<=n;i++)
        {
            scanf("%I64d",&need[i]);
        }
        for(ll i=1;i<=n;i++)
        {
            scanf("%I64d",&have[i]);
        }
        ll ans=0;
        ll mid;
        ll l=0;
        ll r=3000000000ll;
        while(r>=l)
        {
            mid=(l+r)/2;
            if(Slove(mid)==1)
            {
                ans=mid;
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        printf("%I64d\n",ans);
    }
    //cout << "Hello world!" << endl;
    return 0;
}