Реальность жестока, поэтому, хоть в душе вы и экоактивист, но в жизни — простой кассир в кинотеатре. Но не стоить опускать руки, ведь вы еще можете помочь природе!
По работе вам необходимо продать \(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\) чисел — по одному на запрос.
Для каждого запроса выведите минимальное количество билетов, которое вам предстоит продать, чтобы суммарный взнос на экопрограммы достиг хотя бы \(k\), при условии, что вы можете продавать билеты в произвольном порядке.
Если невозможно достигнуть необходимого взноса, даже продав все билеты, выведите \(-1\).
Примечание
В первом запросе общий взнос равен \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|