Петя открыл цветочный магазин. Магазин Пети занимается изготовлением и продажей букетов. Всего существует $$$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 31 01 2 5
1 1 3
5 61 2 1 3 73 1 5 10 15 20
2 1 3 4 5 6
В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.
В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.
Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1.
В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.