A10442 | Magic Powder - 2

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

The first line contains two positive integers $n$ and $k$ ( $1<=n<=100000,1<=k<=10^{9}$ ) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{9}$ ), 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_{1},b_{2},...,b_{n}$ ( $1<=b_{i}<=10^{9}$ ), where the $i$ -th number is equal to the number of grams of the $i$ -th ingredient, which Apollinaria has.

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.