D2. Magic Powder - 2

Time Limit: 1 second

Memory Limit: 256 megabytes

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$ ($n$) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence $a$ ($a$), 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$), 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