D2. Magic Powder - 2

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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 ≤ 100 000, 1 ≤ k ≤ 109) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 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 ≤ bi ≤ 109), 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.

Орчуулсан: [орчуулагдаж байгаа]

Жишээ тэстүүд

Оролт
1 1000000000
1
1000000000
Гаралт
2000000000
Оролт
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1
Гаралт
0
Оролт
3 1
2 1 4
11 3 16
Гаралт
4
Оролт
4 3
4 3 5 6
11 12 14 20
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...