F. Волшебство спасёт мир
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На границе миров открылся портал тёмных сил, и теперь всему миру грозит страшная угроза. Чтобы закрыть портал и спасти мир, нужно сперва победить $$$n$$$ чудовищ, что последовательно вылезают из портала.

Справиться с этим может только волшебница Вика. Она владеет двумя магическими силами — магией воды и магией огня. За секунду Вика может сгенерировать $$$w$$$ единиц водяной маны и $$$f$$$ единиц огненной маны. Мана понадобится ей для создания заклинаний. Изначально у Вики $$$0$$$ единиц водяной маны и $$$0$$$ единиц огненной маны.

Каждое из $$$n$$$ чудовищ, что вылезают из портала, имеет свою силу, выраженную натуральным числом. Чтобы победить $$$i$$$-е чудовище силы $$$s_i$$$, нужно применить заклинание воды или заклинание огня не меньшей силы. Иначе говоря, Вика может потратить не менее единиц $$$s_i$$$ водяной маны на заклинание воды, либо же не менее единиц $$$s_i$$$ огненной маны на заклинание огня.

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

Волшебница хочет спасти мир как можно быстрее, подскажите, сколько времени ей на это понадобится.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке входных содержится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержатся два целых числа $$$w$$$, $$$f$$$ ($$$1 \le w, f \le 10^9$$$) — количество водяной и огненной маны, которое может сгенерировать Вика за секунду.

Во второй строке набора содержится единственное целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество чудовищ.

В третьей строке набора содержится $$$n$$$ натуральных чисел $$$s_1, s_2, s_3, \dots, s_n$$$ ($$$1 \le s_i \le 10^4$$$) — силы чудовищ.

Cумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$100$$$.

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

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

Пример
Входные данные
4
2 3
3
2 6 7
37 58
1
93
190 90
2
23 97
13 4
4
10 10 2 45
Выходные данные
3
2
1
5
Примечание

В первом наборе входных данных Вика может после первой секунды потратить $$$2$$$ единицы огненной маны, чтобы убить первое чудовище. После этого у неё останется $$$2$$$ единицы водяной маны и $$$1$$$ единица огненной. После третьей секунды в её распоряжении будет $$$6$$$ единиц водяной маны и $$$7$$$ огненной маны. Этого хватит, чтобы сразу убить второе и третьей чудовище.