Олимпиадный тренинг

Задача . D2. Волшебный порошок - 2


Задача

Темы: Бинарный поиск реализация *1500

Эта задача предлагается в двух вариантах, которые отличаются только ограничениями. Если вы можете решить эту задачу в больших ограничениях, то вы можете сразу написать одно решение на оба варианта. Если же решение в больших ограничениях вызывает затруднение, вы можете решить только упрощённый вариант.

Проснувшись с утра, Аполлинария решила испечь печенек. Для того чтобы испечь одну печеньку, нужно \(n\) ингредиентов, причем про каждый ингредиент известно число \(a_i\) — сколько грамм этого ингредиента необходимо для того, чтобы испечь одну печеньку. Для приготовления одной печеньки необходимо использовать все \(n\) ингредиентов в нужных пропорциях.

У Аполлинарии есть \(b_i\) грамм \(i\)-го ингридиента. Кроме того, у неё есть \(k\) грамм волшебного порошка. Каждый грамм волшебного порошка можно превратить ровно в \(1\) грамм любого из \(n\) ингредиентов и использовать для приготовления печенек.

Перед вами стоит задача — определить максимальное количество печенек, которое сможет испечь Аполлинария при помощи имеющихся у неё ингредиентов и волшебного порошка.

Входные данные

В первой строке входных данных следуют два целых положительных числа \(n\) и \(k\) (\(1 \le n \le 100\,000, 1 \le k \le 10^9\)) — количество ингредиентов и количество грамм волшебного порошка.

Во второй строке следует последовательность \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)), где \(i\)-е число равно количеству грамм \(i\)-го ингредиента, необходимых для приготовления одной печеньки.

В третьей строке следует последовательность \(b_1, b_2, \dots, b_n\) (\(1 \le b_i \le 10^9\)), где \(i\)-е число равно количеству грамм \(i\)-го ингредиента, которые есть у Аполлинарии.

Выходные данные

Выведите целое число — максимальное количество печенек, которые сможет испечь Аполлинария при помощи волшебного порошка.

Примечание

Первые два примера обращают внимание на более высокие ограничения в сложной версии задачи.

В третьем примере Аполлинарии выгодно превратить \(1\) имеющийся у неё грамм волшебного порошка в ингредиент номер \(2\), тогда она сможет испечь \(4\) печеньки.

Во четвертом примере Аполлинарии выгодно превратить \(1\) грамм волшебного порошка в ингредиент номер \(1\) и \(1\) грамм волшебного порошка в ингредиент номер \(3\). Тогда она сможет испечь \(3\) печеньки. Оставшийся \(1\) грамм волшебного порошка можно оставить, так как с помощью него ответ увеличить невозможно.


Примеры
№Входные данныеВыходные данные
1 1 1000000000
1
1000000000 
2000000000
2 10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1 
0
3 3 1
2 1 4
11 3 16 
4
4 4 3
4 3 5 6
11 12 14 20 
3

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет