Mała D znalazła ostatnio w Internecie niewielką grę. Jej zasady są następujące:
- Celem gry jest zabicie $n$ smoków w kolejności numerów od $1$ do $n$. Każdy smok ma początkową liczbę punktów życia $a_i$ oraz zdolność regeneracji: przy każdym jej użyciu jego liczba punktów życia wzrasta o $p_i$, aż stanie się nieujemna. Smok umiera tylko wtedy, gdy po zakończeniu ataków jego liczba punktów życia wynosi dokładnie $0$.
- Na początku gracz ma $m$ mieczy o znanej sile ataku. W walce z każdym smokiem może wybrać tylko jeden miecz. Po zabiciu smoka ten miecz znika, ale gracz otrzymuje w nagrodę nowy miecz.
Mała D uważa grę za bardzo nudną, lecz gracz, który ukończy ją najszybciej, otrzyma prawo udziału w ION2018. Postanowiła więc napisać prostego robota, który ukończy ją za nią. Robot przestrzega następujących zasad:
- Do walki z każdym smokiem wybiera spośród posiadanych mieczy ten o największej sile ataku nieprzekraczającej początkowej liczby punktów życia smoka. Jeśli takiego miecza nie ma, wybiera miecz o najmniejszej sile ataku.
- Każdego smoka atakuje wybranym mieczem stałą liczbę $x$ razy, zmniejszając jego liczbę punktów życia o $x\times ATK$.
- Następnie smok wielokrotnie używa regeneracji, odzyskując za każdym razem $p_i$ punktów życia. Jeśli przed regeneracją lub po którymś jej użyciu ma dokładnie $0$ punktów życia, umiera, a gracz przechodzi ten etap.
Liczba ataków robota jest więc kluczowa dla możliwie szybkiego ukończenia gry. Mała D zna już wszystkie właściwości każdego smoka i chce cię sprawdzić: jaką wartość $x$ należy ustawić, aby ukończyć grę przy najmniejszej liczbie ataków?
Jeśli żadna wartość nie pozwala ukończyć gry, wypisz $-1$.
Wejście
Dane należy wczytać z pliku dragon.in.
Pierwszy wiersz zawiera liczbę całkowitą $T$, oznaczającą liczbę zestawów danych.
Następuje $T$ zestawów danych, każdy złożony z pięciu wierszy.
- Pierwszy wiersz każdego zestawu zawiera dwie liczby całkowite $n,m$: liczbę smoków i początkową liczbę mieczy.
- Następny wiersz zawiera $n$ dodatnich liczb całkowitych; $i$-ta z nich to początkowa liczba punktów życia $a_i$ smoka numer $i$.
- Następny wiersz zawiera $n$ dodatnich liczb całkowitych; $i$-ta z nich to wartość regeneracji $p_i$ smoka numer $i$.
- Następny wiersz zawiera $n$ dodatnich liczb całkowitych; $i$-ta z nich to siła ataku miecza otrzymywanego za zabicie smoka numer $i$.
- Następny wiersz zawiera $m$ dodatnich liczb całkowitych, oznaczających siły ataku $m$ początkowych mieczy.
Wyjście
Wyniki należy wypisać do pliku dragon.out.
Wyjście zawiera $T$ wierszy.
Wiersz $i$ zawiera jedną liczbę całkowitą: najmniejszą liczbę ataków $x$ pozwalającą robotowi ukończyć grę w $i$-tym zestawie danych. Jeśli odpowiedź nie istnieje, wypisz $-1$.
Przykład
Wejście 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
Wyjście 1
59 -1
Uwagi
Pierwszy zestaw danych:
- Początkowe siły ataku mieczy to $\{1,9,10\}$. Pierwszy smok ma $3$ punkty życia, więc wybieramy miecz o sile $1$. Po $59$ atakach zadajemy $59$ obrażeń, pozostawiając smokowi $-56$ punktów życia. Po $14$ regeneracjach ma dokładnie $0$ punktów życia i umiera.
- Miecz o sile $1$ znika, a podnosimy miecz o sile $7$. Posiadane siły ataku to teraz $\{7,9,10\}$. Drugi smok ma $5$ punktów życia, więc wybieramy miecz o sile $7$. Po $59$ atakach zadajemy $413$ obrażeń, pozostawiając smokowi $-408$ punktów życia. Po $68$ regeneracjach ma dokładnie $0$ punktów życia i umiera.
- Posiadane siły ataku to teraz $\{3,9,10\}$. Trzeci smok ma $7$ punktów życia, więc wybieramy miecz o sile $3$. Po $59$ atakach zadajemy $177$ obrażeń, pozostawiając smokowi $-170$ punktów życia. Po $17$ regeneracjach ma dokładnie $0$ punktów życia i umiera.
- Nie można ukończyć gry przy mniej niż $59$ atakach, więc odpowiedź wynosi $59$.
Drugi zestaw danych:
- Nie istnieje sposób pozwalający zabić zarówno pierwszego, jak i drugiego smoka, więc nie można ukończyć gry i wypisujemy $-1$.
Przykład 2
Zobacz pliki dragon/dragon2.in i dragon/dragon2.ans w katalogu zawodnika.
Podzadania
| Numer testu | $n$ | $m$ | $p_i$ | $a_i$ | Siła ataku | Inne ograniczenia |
|---|---|---|---|---|---|---|
| $1$ | .h=5 $\le10^5$ | .h=5 $=1$ | .h=5 $=1$ | .h=7 $\le10^5$ | .h=2 $=1$ | .h=5 Brak |
| $2$ | ||||||
| $3$ | .h=5 $\le10^5$ | |||||
| $4$ | ||||||
| $5$ | ||||||
| $6$ | .h=2 $\le10^3$ | .h=2 $\le10^3$ | .h=2 $\le10^5$ | .h=2 Właściwość 1, właściwość 2 | ||
| $7$ | ||||||
| $8$ | .h=5 $=1$ | .h=5 $=1$ | .h=5 $\le10^8$ | .h=8 $\le10^8$ | .h=13 $\le10^6$ | .h=5 Właściwość 1 |
| $9$ | ||||||
| $10$ | ||||||
| $11$ | ||||||
| $12$ | ||||||
| $13$ | .h=3 $=10^5$ | .h=3 $=10^5$ | .h=3 $=1$ | .h=3 Brak szczególnych ograniczeń | ||
| $14$ | ||||||
| $15$ | ||||||
| $16$ | .h=5 $\le10^5$ | .h=5 $\le10^5$ | .h=2 Wszystkie $p_i$ są pierwsze | .h=5 $\le10^{12}$ | .h=5 Właściwość 1 | |
| $17$ | ||||||
| $18$ | .h=3 Brak szczególnych ograniczeń | |||||
| $19$ | ||||||
| $20$ |
Właściwość 1 oznacza, że dla każdego $i$ zachodzi $a_i\le p_i$.
Właściwość 2 oznacza, że $\operatorname{LCM}(p_i)\le10^6$, czyli najmniejsza wspólna wielokrotność wszystkich $p_i$ nie przekracza $10^6$.
Dla wszystkich testów zachodzi $T\le5$, siła ataku każdej broni nie przekracza $10^6$, a najmniejsza wspólna wielokrotność wszystkich $p_i$ nie przekracza $10^{12}$.
Uwagi
Wyniki pośrednie mogą być bardzo duże. Zwróć uwagę na typ zmiennych, w których je przechowujesz.