小 D недавно нашла в интернете небольшую игру. Её правила таковы:
- Цель игры — убить $n$ драконов в порядке номеров от $1$ до $n$. Начальное здоровье $i$-го дракона равно $a_i$. Каждый дракон умеет восстанавливаться: при использовании этой способности его здоровье каждый раз увеличивается на $p_i$, пока не станет неотрицательным. Дракон умирает только после окончания атаки и только если его здоровье в точности равно $0$.
- В начале игры у игрока есть $m$ мечей с известной силой атаки. Для сражения с каждым драконом игрок может выбрать только один меч. После убийства дракона этот меч исчезает, но в награду игрок получает новый меч.
小 D считает игру очень скучной, однако игрок, который пройдёт её быстрее всех, получит право участвовать в ION2018. Поэтому 小 D решила написать простенького робота, который пройдёт игру за неё. Её робот следует таким правилам:
- Перед каждым драконом робот выбирает из имеющихся мечей меч с наибольшей силой атаки, не превышающей начальное здоровье дракона. Если такого меча нет, он выбирает меч с наименьшей силой атаки.
- Для каждого дракона робот использует выбранный на предыдущем шаге меч и атакует ровно $x$ раз, уменьшая здоровье дракона на $x\times ATK$.
- Затем дракон многократно применяет способность восстановления, каждый раз восстанавливая $p_i$ здоровья. Если до первого восстановления или после какого-либо восстановления его здоровье равно $0$, дракон умирает и игрок проходит этот уровень.
Очевидно, число атак робота определяет, удастся ли пройти игру быстрее всех. 小 D теперь знает все характеристики каждого дракона и хочет испытать вас: какое число атак $x$ нужно установить роботу, чтобы пройти игру с наименьшим числом атак?
Если пройти игру невозможно при любом значении этого параметра, выведите -1.
Входные данные
Данные считываются из файла dragon.in.
Первая строка содержит целое число $T$ — количество наборов данных.
Далее следуют $T$ наборов данных, каждый из которых содержит 5 строк.
- Первая строка набора содержит два целых числа $n$ и $m$ — количество драконов и начальное количество мечей.
- Следующая строка содержит $n$ положительных целых чисел. Число на $i$-й позиции задаёт начальное здоровье $a_i$ дракона с номером $i$.
- Следующая строка содержит $n$ положительных целых чисел. Число на $i$-й позиции задаёт способность восстановления $p_i$ дракона с номером $i$.
- Следующая строка содержит $n$ положительных целых чисел. Число на $i$-й позиции задаёт силу атаки меча, получаемого в награду за убийство дракона с номером $i$.
- Следующая строка содержит $m$ положительных целых чисел — силы атаки $m$ мечей, имеющихся в начале игры.
Выходные данные
Результат выводится в файл dragon.out.
Выведите $T$ строк.
В $i$-й строке выведите одно целое число — наименьшее число атак $x$, при котором робот сможет пройти игру для $i$-го набора данных. Если ответа не существует, выведите -1.
Примеры
Входные данные 1
2 3 3 3 5 7 4 6 10 7 3 9 1 9 1000 3 2 3 5 6 4 8 7 1 1 1 1 1
Выходные данные 1
59 -1
Примечание
Первый набор данных:
- Изначально силы атаки мечей равны $\{1,9,10\}$. Здоровье первого дракона равно $3$, поэтому выбирается меч с силой атаки $1$. После 59 атак он наносит $59$ единиц урона, и здоровье дракона становится равным $-56$. После 14 восстановлений здоровье становится в точности равным $0$, и дракон умирает.
- Меч с силой атаки $1$ исчезает, и игрок подбирает меч с силой атаки $7$. Теперь силы атаки имеющихся мечей равны $\{7,9,10\}$. Здоровье второго дракона равно $5$, поэтому выбирается меч с силой атаки $7$. После 59 атак он наносит $413$ единиц урона, и здоровье дракона становится равным $-408$. После 68 восстановлений здоровье становится в точности равным $0$, и дракон умирает.
- Теперь силы атаки имеющихся мечей равны $\{3,9,10\}$. Здоровье третьего дракона равно $7$, поэтому выбирается меч с силой атаки $3$. После 59 атак он наносит $177$ единиц урона, и здоровье дракона становится равным $-170$. После 17 восстановлений здоровье становится в точности равным $0$, и дракон умирает.
- Пройти игру менее чем за 59 атак невозможно, поэтому ответ равен $59$.
Второй набор данных:
- Не существует способа убить и первого, и второго дракона, поэтому пройти игру невозможно и выводится
-1.
Пример 2
См. файлы dragon/dragon2.in и dragon/dragon2.ans в каталоге участника.
Подзадачи
| Номер теста | $n$ | $m$ | $p_i$ | $a_i$ | Сила атаки | Другие ограничения |
|---|---|---|---|---|---|---|
| 1 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | Нет |
| 2 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | Нет |
| 3 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | Нет |
| 4 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | Нет |
| 5 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Свойства 1 и 2 |
| 6 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Свойства 1 и 2 |
| 7 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Свойства 1 и 2 |
| 8 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Свойство 1 |
| 9 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Свойство 1 |
| 10 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Свойство 1 |
| 11 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Свойство 1 |
| 12 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Свойство 1 |
| 13 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Свойство 1 |
| 14 | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | Без особых ограничений |
| 15 | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | Без особых ограничений |
| 16 | $\le 10^5$ | $\le 10^5$ | Все $p_i$ — простые числа | $\le 10^{12}$ | $\le 10^6$ | Свойство 1 |
| 17 | $\le 10^5$ | $\le 10^5$ | Все $p_i$ — простые числа | $\le 10^{12}$ | $\le 10^6$ | Свойство 1 |
| 18 | $\le 10^5$ | $\le 10^5$ | Без особых ограничений | $\le 10^{12}$ | $\le 10^6$ | Свойство 1 |
| 19 | $\le 10^5$ | $\le 10^5$ | Без особых ограничений | $\le 10^{12}$ | $\le 10^6$ | Свойство 1 |
| 20 | $\le 10^5$ | $\le 10^5$ | Без особых ограничений | $\le 10^{12}$ | $\le 10^6$ | Свойство 1 |
Свойство 1 означает: для любого $i$ выполняется $a_i\le p_i$.
Свойство 2 означает: $\operatorname{LCM}(p_i)\le 10^6$, то есть наименьшее общее кратное всех $p_i$ не превышает $10^6$.
Для всех тестов $T\le 5$, сила атаки любого оружия не превышает $10^6$, а наименьшее общее кратное всех $p_i$ не превышает $10^{12}$.
Примечание
Промежуточные результаты могут быть очень большими. Обратите внимание на тип переменных, в которых они хранятся.