codeforces 350 div2 D Magic Powder - 2 二分

Magic Powder - 2

Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Submit  Status

Description

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.

Sample Input

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项材料，但你拥有k个魔法材料，可以转换成任何材料，现你有有的材料给你，问最多能制造多少东西

直接二分查找最大能制造的饼干数，把上界设的2*10^9+1；最后你可能相差1，判断一下所需魔法材料是否超过k
#include<stdio.h>       
__int64 a[2000000],b[20000000];    
int max=2*1e9+2; //二分时最大边界    
__int64 n,k;    
__int64 judge(__int64 l,__int64 r)    
{      
    __int64 mid,sum;      
    while(l <= r)    
    {      
        mid = ( l + r) / 2 ,sum = 0;      
        for (int i = 0 ; i < n ; i++ )         
        {      
            sum += a[i] * mid - b[i] > 0 ? a[i] * mid - b[i] : 0 ;      
            if( sum > k) //判断所需材料是否超过k   
                break;     
        }      
        if(sum == k)    
            return mid;      
        else if(sum < k)    
            l = mid + 1;      
        else     
            r = mid - 1;      
    }      
    return r;      
}     
int main()     
{    
        
    while (~scanf("%I64d %I64d",&n,&k))    
    {    
        for (int i = 0 ; i < n ; i++)    
        {    
            scanf("%I64d",&a[i]);    
        }    
        for (int i = 0 ; i < n ; i++ )    
        {    
            scanf("%I64d",&b[i]);    
        }    
        printf("%I64d\n",judge(1,max));    
    }    
      
}