2339.Magic Powder - 2

Time Limit: 1s Memory Limit: 256MB

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

Input Format(From the terminal/stdin)

The first line contains two positive integers n and k (1 \le n \le 100000,1 \le k \le 109) - the number of ingredients and the number of grams of the magic powder.

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

Output Format(To the terminal/stdout)

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 1

Copy 
1 1000000000
1
1000000000
 ·          \n
 \n
          \n

Sample Output 1

Copy 
2000000000
          \n

Sample Input 2

Copy 
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1
  · \n
          ·          ·          ·          ·          ·          ·          ·          ·          ·          \n
 · · · · · · · · · \n

Sample Output 2

Copy 
0
 \n

Sample Input 3

Copy 
3 1
2 1 4
11 3 16
 · \n
 · · \n
  · ·  \n

Sample Output 3

Copy 
4
 \n

Sample Input 4

Copy 
4 3
4 3 5 6
11 12 14 20
 · \n
 · · · \n
  ·  ·  ·  \n

Sample Output 4

Copy 
3
 \n

Submit

请先 登录
 Submit
题解(0)
© 2025 FAQs