Цветочный магазин
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Петя открыл цветочный магазин. Магазин Пети занимается изготовлением и продажей букетов. Всего существует $$$n$$$ видов цветов, занумерованных от 1 до $$$n$$$. Каждый букет, чтобы быть гармоничным и красивым, должен состоять из цветов всех видов, по одной штуке каждого вида. В магазине уже есть $$$a_i$$$ штук цветов вида $$$i$$$. На цветочной базе можно купить цветок любого вида за 1 рубль.

Определите, сколько букетов сможет собрать Петя, если потратит не более $$$x$$$ рублей на покупку цветов на базе. Ответьте на $$$q$$$ запросов с различными $$$x_i$$$.

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

В первой строке входных данных находятся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — количество различных типов цветов и количество запросов.

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \cdots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — количество цветов каждого вида, имеющихся в магазине.

В третьей строке находятся $$$q$$$ целых чисел $$$x_1, x_2, \cdots, x_q$$$ ($$$0 \le x_i \le 10^9$$$) — запросы Пети.

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

Выходной файл должен содержать $$$q$$$ чисел, где $$$i$$$-е число это максимальное количество букетов, которое можно собрать потратив не более $$$x_i$$$ рублей.

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

Задача состоит из 20 тестов, не считая тестов из условия. Все тесты можно разделить на следующие группы:

ГруппаМакс. баллДоп. ограниченияКомментарий
$$$0$$$$$$0$$$Тесты из условия
$$$1$$$$$$18$$$Все $$$a_i$$$ равны между собой
$$$2$$$$$$30$$$$$$n, q \le 100$$$, $$$a_i, x_i \le 100$$$
$$$3$$$$$$28$$$$$$n \le 1000$$$, $$$q \le 100$$$
$$$4$$$$$$24$$$

Примеры

Входные данные
2 3
1 0
1 2 5
Выходные данные
1 1 3 
Входные данные
5 6
1 2 1 3 7
3 1 5 10 15 20
Выходные данные
2 1 3 4 5 6 

Примечание

В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.

В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.

Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1.

В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.