Statement is not available in English language
D. Охота на монстра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы счастливый мэр процветающей столицы Берляндии, но вот незадача — в пригороде поселился ужасный монстр, который атакует торговые караваны, курсирующие между столицей и соседними городами. Чтобы избавиться от монстра, вы решили нанять команду героев в городской гильдии авантюристов.

Гильдия предлагает $$$n$$$ воинов и у $$$i$$$-го воина $$$h_i$$$ единиц здоровья и $$$d_i$$$ единиц атаки. У монстра, которого надо убить, $$$a$$$ единиц здоровья.

Пока у монстра осталось положительное число единиц здоровья и остался хотя бы один герой с положительным количеством единиц здоровья, происходит следующее:

  1. Сначала каждый живой герой наносит монстру урон, равный значению его атаки. Если здоровье монстра упало до нуля, битва завершается;
  2. Затем, если монстр еще жив, он наносит каждому герою по единице урона. Каждый герой, чей уровень здоровья упал до нуля, умирает.

Так как казна ограничена, вы хотите нанять наименьшее число героев, чтобы убить монстра. Но вы также не хотите, чтобы умер хотя бы один из героев команды, поэтому вам надо нанять наименьшее число героев, чтобы они могли убить монстра без потерь.

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

В первой строке входные данных содержится одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Далее следует описание наборов.

В первой строке каждого набора содержится целое число $$$a$$$ ($$$1 \leq a \leq 10^9$$$) — здоровье монстра.

Во второй строке каждого набора содержится целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — общее число воинов, которых предлагает гильдия для найма.

В третьей строке каждого набора содержатся $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \leq h_i \leq 10^9$$$) — единицы здоровья каждого героя.

В четвертой строке каждого набора содержатся $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ ($$$1 \leq d_i \leq 10^9$$$) — единицы атаки каждого героя.

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

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

Для каждого набора входных данных в отдельной строке выведите единственное целое число:

  • минимальное количество героев, которое нужно нанять, чтобы убить монстра без потерь,
  • или $$$-1$$$, если это невозможно.
Пример
Входные данные
2
12
5
1 2 3 3 4
2 4 1 1 1
10
1
1
14
Выходные данные
3
1
Примечание

В первом наборе входных данных достаточно трёх героев, чтобы убить монстра без потерь. Например, это могут быть герои с номерами $$$2$$$, $$$3$$$, $$$4$$$. Их суммарная атака равна $$$6$$$ и они убивают монстра за две атаки.

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