小 D hat kürzlich im Internet ein kleines Spiel entdeckt. Die Regeln sind wie folgt:
- Ziel ist es, $n$ riesige Drachen in der Reihenfolge ihrer Nummern $1$ bis $n$ zu töten. Jeder Drache besitzt anfangs $a_i$ Lebenspunkte. Außerdem kann er sich regenerieren: Bei jeder Regeneration steigen seine Lebenspunkte um $p_i$, bis sie nichtnegativ sind. Er stirbt nur, wenn seine Lebenspunkte nach Abschluss der Angriffe genau $0$ betragen.
- Zu Beginn besitzt der Spieler $m$ Schwerter mit bekannten Angriffswerten. Für jeden Drachen darf der Spieler nur ein Schwert wählen. Nachdem der Drache getötet wurde, verschwindet dieses Schwert. Als Belohnung erhält der Spieler jedoch ein neues Schwert.
小 D findet das Spiel sehr langweilig, aber der Spieler, der es am schnellsten abschließt, erhält die Teilnahmeberechtigung für ION2018. Deshalb beschließt 小 D, einen einfachen Roboter zu programmieren, der das Spiel für sie abschließt. Ihr Roboter befolgt diese Regeln:
- Vor jedem Drachen wählt der Roboter unter seinen derzeitigen Schwertern mit Angriffswert höchstens gleich den anfänglichen Lebenspunkten des Drachen das mit dem größten Angriffswert. Gibt es kein solches Schwert, wählt er das Schwert mit dem kleinsten Angriffswert.
- Gegen jeden Drachen greift der Roboter mit dem im vorherigen Schritt gewählten Schwert eine feste Anzahl $x$ von Malen an. Dadurch sinken die Lebenspunkte des Drachen um $x\times ATK$.
- Anschließend regeneriert sich der Drache wiederholt und erhält jedes Mal $p_i$ Lebenspunkte zurück. Sind seine Lebenspunkte vor der ersten Regeneration oder nach irgendeiner Regeneration gleich $0$, stirbt der Drache und der Spieler besteht diesen Abschnitt.
Offensichtlich entscheidet die Anzahl der Angriffe des Roboters darüber, ob er das Spiel am schnellsten abschließen kann. 小 D kennt nun alle Eigenschaften jedes Drachen und möchte dich auf die Probe stellen: Auf welchen Wert muss die Anzahl $x$ der Angriffe des Roboters gesetzt werden, damit er das Spiel mit möglichst wenigen Angriffen abschließt?
Lässt sich das Spiel für keinen Wert abschließen, gib einfach -1 aus.
Eingabe
Lies die Daten aus der Datei dragon.in.
Die erste Zeile enthält eine ganze Zahl $T$, die Anzahl der Datensätze.
Es folgen $T$ Datensätze, die jeweils aus 5 Zeilen bestehen.
- Die erste Zeile jedes Datensatzes enthält zwei ganze Zahlen $n$ und $m$, die Anzahl der Drachen und die anfängliche Anzahl der Schwerter.
- Die nächste Zeile enthält $n$ positive ganze Zahlen. Die $i$-te Zahl gibt die anfänglichen Lebenspunkte $a_i$ des $i$-ten Drachen an.
- Die nächste Zeile enthält $n$ positive ganze Zahlen. Die $i$-te Zahl gibt die Regenerationsfähigkeit $p_i$ des $i$-ten Drachen an.
- Die nächste Zeile enthält $n$ positive ganze Zahlen. Die $i$-te Zahl gibt den Angriffswert des Schwertes an, das man als Belohnung für das Töten des $i$-ten Drachen erhält.
- Die nächste Zeile enthält $m$ positive ganze Zahlen, die Angriffswerte der $m$ anfänglich vorhandenen Schwerter.
Ausgabe
Schreibe die Ausgabe in die Datei dragon.out.
Gib insgesamt $T$ Zeilen aus.
Die $i$-te Zeile enthält eine ganze Zahl: die kleinste Anzahl $x$ der Angriffe, mit der der Roboter das Spiel für den $i$-ten Datensatz abschließen kann. Existiert keine Antwort, gib -1 aus.
Beispiele
Eingabe 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
Ausgabe 1
59 -1
Hinweis
Erster Datensatz:
- Anfangs haben die vorhandenen Schwerter die Angriffswerte $\{1,9,10\}$. Der 1. Drache besitzt $3$ Lebenspunkte. Daher wird das Schwert mit Angriffswert $1$ gewählt. Nach $59$ Angriffen hat es $59$ Schaden verursacht, und der Drache hat $-56$ Lebenspunkte. Nach $14$ Regenerationen hat er genau $0$ Lebenspunkte und stirbt.
- Das Schwert mit Angriffswert $1$ verschwindet, und ein Schwert mit Angriffswert $7$ wird aufgenommen. Die vorhandenen Schwerter haben nun die Angriffswerte $\{7,9,10\}$. Der 2. Drache besitzt $5$ Lebenspunkte. Daher wird das Schwert mit Angriffswert $7$ gewählt. Nach $59$ Angriffen hat es $413$ Schaden verursacht, und der Drache hat $-408$ Lebenspunkte. Nach $68$ Regenerationen hat er genau $0$ Lebenspunkte und stirbt.
- Die vorhandenen Schwerter haben nun die Angriffswerte $\{3,9,10\}$. Der 3. Drache besitzt $7$ Lebenspunkte. Daher wird das Schwert mit Angriffswert $3$ gewählt. Nach $59$ Angriffen hat es $177$ Schaden verursacht, und der Drache hat $-170$ Lebenspunkte. Nach $17$ Regenerationen hat er genau $0$ Lebenspunkte und stirbt.
- Mit weniger als $59$ Angriffen lässt sich das Spiel nicht abschließen. Die Antwort lautet daher $59$.
Zweiter Datensatz:
- Es gibt keine Möglichkeit, sowohl den ersten als auch den zweiten Drachen zu töten. Das Spiel lässt sich also nicht abschließen; gib
-1aus.
Beispiel 2
Siehe dragon/dragon2.in und dragon/dragon2.ans im Teilnehmerverzeichnis.
Teilaufgaben
| Testfallnummer | $n$ | $m$ | $p_i$ | $a_i$ | Angriffswert | Weitere Einschränkungen |
|---|---|---|---|---|---|---|
| 1 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | Keine |
| 2 | ||||||
| 3 | $\le 10^5$ | |||||
| 4 | ||||||
| 5 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | Eigenschaft 1, Eigenschaft 2 | ||
| 6 | ||||||
| 7 | $\le 10^8$ | |||||
| 8 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^6$ | Eigenschaft 1 | |
| 9 | ||||||
| 10 | ||||||
| 11 | ||||||
| 12 | ||||||
| 13 | ||||||
| 14 | $=10^5$ | $=10^5$ | $=1$ | Keine besonderen Einschränkungen | ||
| 15 | ||||||
| 16 | $\le 10^5$ | $\le 10^5$ | Alle $p_i$ sind Primzahlen | $\le 10^{12}$ | Eigenschaft 1 | |
| 17 | ||||||
| 18 | Keine besonderen Einschränkungen | |||||
| 19 | ||||||
| 20 |
Eigenschaft 1 bedeutet: Für jedes $i$ gilt $a_i\le p_i$.
Eigenschaft 2 bedeutet: $\operatorname{LCM}(p_i)\le 10^6$, das heißt, das kleinste gemeinsame Vielfache aller $p_i$ ist höchstens $10^6$.
Für alle Testfälle gilt $T\le 5$. Alle Waffen haben einen Angriffswert von höchstens $10^6$, und das kleinste gemeinsame Vielfache aller $p_i$ ist höchstens $10^{12}$.
Hinweis
Die von dir berechneten Zwischenergebnisse können sehr groß sein. Achte auf die Datentypen der Variablen, in denen du sie speicherst.