C. Спаси природу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Реальность жестока, поэтому, хоть в душе вы и экоактивист, но в жизни — простой кассир в кинотеатре. Но не стоить опускать руки, ведь вы еще можете помочь природе!

По работе вам необходимо продать $$$n$$$ билетов. Цена $$$i$$$-го билета равна $$$p_i$$$. Как продавец, вы можете выбрать порядок (то есть перестановку), в котором будут продаваться билеты. Вы узнали, что ваш кинотеатр участвует в двух экологических программах, применяя их к порядку, который выбрали вы:

  • $$$x\%$$$ цены каждого $$$a$$$-го проданного билета ($$$a$$$-й, $$$2a$$$-й, $$$3a$$$-й и так далее билеты) в вашем порядке будет направлено на разработку и продвижение возобновляемых источников энергии.
  • $$$y\%$$$ цены каждого $$$b$$$-го проданного билета ($$$b$$$-й, $$$2b$$$-й, $$$3b$$$-й и так далее билеты) в вашем порядке будет направлено на борьбу с загрязнением окружающей среды.

Если билет попал в обе программы одновременно, то в сумме $$$(x + y) \%$$$ будет направлено на сохранение природы. Также, известно, что все цены билетов кратны $$$100$$$, а потому нет проблем с округлениями.

Например, если вам надо продать билеты с ценами $$$[400, 100, 300, 200]$$$, а кинотеатр отдает $$$10\%$$$ от каждого $$$2$$$-го проданного билета и $$$20\%$$$ от каждого $$$3$$$-го проданного билета, то, продав их в порядке $$$[100, 200, 300, 400]$$$ вы отправите на благое дело $$$100 \cdot 0 + 200 \cdot 0.1 + 300 \cdot 0.2 + 400 \cdot 0.1 = 120$$$. Однако, выбрав порядок $$$[100, 300, 400, 200]$$$, можно набрать $$$100 \cdot 0 + 300 \cdot 0.1 + 400 \cdot 0.2 + 200 \cdot 0.1 = 130$$$.

Природа не может ждать, а потому вы решили изменить порядок продажи билетов таким образом, что суммарный взнос в обе программы достигнет значения хотя бы $$$k$$$ за минимальное количество проданных билетов. Либо скажите, что это невозможно. Другими словами, найдите минимальное количество билетов, которые нужно продать, чтобы заработать как минимум $$$k$$$.

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

В первой строке задано единственное целое число $$$q$$$ ($$$1 \le q \le 100$$$) — количество независимых запросов. Каждый запрос состоит из $$$5$$$ строк.

В первой строке каждого запроса содержится единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество билетов.

Во второй строке заданы $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$100 \le p_i \le 10^9$$$, $$$p_i \bmod 100 = 0$$$) — соответствующие цены билетов.

В третьей строке заданы два целых числа $$$x$$$ и $$$a$$$ ($$$1 \le x \le 100$$$, $$$x + y \le 100$$$, $$$1 \le a \le n$$$) — параметры первой программы.

В четвертой строке заданы два целых числа $$$y$$$ и $$$b$$$ ($$$1 \le y \le 100$$$, $$$x + y \le 100$$$, $$$1 \le b \le n$$$) — параметры второй программы.

В пятой строке задано единственное целое число $$$k$$$ ($$$1 \le k \le 10^{14}$$$) — суммарный необходимый взнос.

Гарантируется, что суммарное количество билетов в одном тесте не превосходит $$$2 \cdot 10^5$$$.

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

Выведите $$$q$$$ чисел — по одному на запрос.

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

Если невозможно достигнуть необходимого взноса, даже продав все билеты, выведите $$$-1$$$.

Пример
Входные данные
4
1
100
50 1
49 1
100
8
100 200 100 200 100 200 100 100
10 2
15 3
107
3
1000000000 1000000000 1000000000
50 1
50 1
3000000000
5
200 100 100 100 100
69 5
31 2
90
Выходные данные
-1
6
3
4
Примечание

В первом запросе общий взнос равен $$$50 + 49 = 99 < 100$$$, поэтому собрать необходимую сумму невозможно.

Во втором запросе вы можете выбрать порядок следующим образом: $$$[100, 100, 200, 200, 100, 200, 100, 100]$$$ и общий взнос от первых $$$6$$$ проданных билетов будет равен $$$100 \cdot 0 + 100 \cdot 0.1 + 200 \cdot 0.15 + 200 \cdot 0.1 + 100 \cdot 0 + 200 \cdot 0.25 = 10 + 30 + 20 + 50 = 110$$$.

В третьем запросе вся стоимость билета идет на защиту экологии.

В четвертом запросе вы можете выбрать порядок как $$$[100, 200, 100, 100, 100]$$$ и суммарный взнос за первые $$$4$$$ билета будет равен $$$100 \cdot 0 + 200 \cdot 0.31 + 100 \cdot 0 + 100 \cdot 0.31 = 62 + 31 = 93$$$.