小D нещодавно знайшла в інтернеті невелику гру. Її правила такі:
- Мета гри — вбити $n$ драконів у порядку їхніх номерів від $1$ до $n$. Кожен дракон має початкове здоров'я $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
Перший набір даних:
- Спочатку сили атаки наявних мечів дорівнюють $\{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, 2 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | Немає |
| 3, 4 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | Немає |
| 5, 6, 7 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Властивості 1 і 2 |
| 8, 9, 10, 11, 12, 13 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Властивість 1 |
| 14, 15 | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | Без додаткових обмежень |
| 16, 17 | $\le 10^5$ | $\le 10^5$ | Усі $p_i$ — прості числа | $\le 10^{12}$ | $\le 10^6$ | Властивість 1 |
| 18, 19, 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}$.
Примітка
Проміжні результати ваших обчислень можуть бути дуже великими. Зверніть увагу на типи змінних, у яких ви їх зберігаєте.