408801: GYM103325 E День рождения

E. День рожденияограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Саша очень любит настольные игры, особенно игру «Ticket to Ride». Сашины друзья однако не разделяют её энтузиазма, а больше всего им не нравится запоминать новые правила в очередном дополнении к игре.

Специально для таких случаев (когда никто не хочет запоминать сложные правила) Саша придумала свою собственную вариацию игры — правила в ней очень простые, а для игры нужны только карточки с разноцветными вагонами.

Скоро у Саши день рождения и она собирается позвать всех своих многочисленных друзей и устроить вечер игры в «Ticket to Ride» (точнее, в свою упрощённую версию игры). Однако у Саши есть проблема: каждому игроку потребуется по $$$a_i$$$ карточек каждого из $$$n$$$ цветов, а у неё их ограниченное число: всего $$$b_i$$$ штук. К счастью, дополнительно у Саши имеется ещё $$$k$$$ локомотивов — карт-джокеров, которые можно использовать вместо любого цвета.

Саша хочет позвать как можно больше своих друзей на день рождения, помогите ей понять, сколько человек сможет одновременно играть с ней в «Ticket to Ride».

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

В первой строке входных данных следуют два целых положительных числа $$$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$$$-го цвета в наличии у Саши.

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

Выведите одно целое число — сколько человек Саша может позвать на праздник (включая её саму).

Система оценки

$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } &\text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \\ \hline 1 & 46 & n, k, a_i, b_i \le 1000 & \text {}\\ \hline 2 & 54 & \text { Нет дополнительных ограничений } & \text {1}\\ \hline \end{array}$$$$$$

ПримерыВходные данные

3 1
2 1 4
11 3 16

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

4

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

4 3
4 3 5 6
11 12 14 20

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

3

Примечание

Тесты к этой задаче состоят из 2 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.