Magic Powder - 2

Description:

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:

1 1000000000
1
1000000000

Sample Output:

2000000000

Sample Input:

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

Sample Output:

0

Sample Input:

3 1
2 1 4
11 3 16

Sample Output:

4

Sample Input:

4 3
4 3 5 6
11 12 14 20

Sample Output:

3