Codeforces 670D2 Magic Powder - 2【二分】

D2. Magic Powder - 2

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 ≤ 10⁹) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹), 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₁, b₂, ..., b_n (1 ≤ b_i ≤ 10⁹), 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

题目大意：

给你N种材料，以及M个魔法材料。

每个魔法材料可以变成任意一种魔法材料。

现在已知做一个饼干要用每种材料Ai个，而且已知每种饼干我们初始有Bi个。

问最多可以做出来多少饼干。

思路：

明显如果我们能够做出来x个饼干，那么一定能够做出来x-1个饼干，同理x-2也一定能够做出来。

所以这里一定有一个单调性在这里边。

那么我们二分结果，然后check一下就行。

注意数据范围。

Ac代码：

#include<stdio.h>
#include<string.h>
using namespace std;
#define ll __int64
ll n,m;
ll a[150000];
ll b[150000];
ll Slove(ll mid)
{
    ll sum=0;
    for(ll i=0;i<n;i++)
    {
        if(b[i]-a[i]*mid<0)sum+=b[i]-a[i]*mid;
        if(-sum>m)return 0;
    }
    if(sum>=0)return 1;
    if(sum<0&&-sum<=m)return 1;
    return 0;
}
int main()
{
    while(~scanf("%I64d%I64d",&n,&m))
    {
        for(ll i=0;i<n;i++)scanf("%I64d",&a[i]);
        for(ll i=0;i<n;i++)scanf("%I64d",&b[i]);
        ll ans=0;
        ll l=0;
        ll r=2000000000;
        while(r-l>=0)
        {
            ll mid=(l+r)/2;
            if(Slove(mid)==1)
            {
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        printf("%I64d\n",ans);
    }
}