小 D a récemment découvert un petit jeu en ligne. Ses règles sont les suivantes :
- Le but est de tuer $n$ dragons dans l'ordre de leurs numéros, de $1$ à $n$. Le dragon $i$ possède initialement $a_i$ points de vie. Chaque dragon possède aussi une capacité de régénération : lorsqu'il l'utilise, ses points de vie augmentent de $p_i$ à chaque fois, jusqu'à devenir non négatifs. Il ne meurt qu'une fois les attaques terminées, et uniquement si ses points de vie valent exactement $0$.
- Au début du jeu, le joueur possède $m$ épées dont les puissances d'attaque sont connues. Face à chaque dragon, il ne peut choisir qu'une seule épée. Après la mort du dragon, cette épée disparaît, mais le joueur reçoit en récompense une nouvelle épée.
小 D trouve ce jeu très ennuyeux, mais le joueur qui le termine le plus rapidement peut obtenir une qualification pour ION2018. Elle décide donc d'écrire un robot un peu naïf pour le terminer à sa place. Son robot suit les règles suivantes :
- Face à un dragon, le robot choisit, parmi les épées actuellement possédées dont la puissance d'attaque ne dépasse pas les points de vie initiaux du dragon, celle ayant la puissance d'attaque maximale. S'il n'en existe aucune, il choisit l'épée de puissance d'attaque minimale.
- Face à chaque dragon, le robot utilise l'épée choisie à l'étape précédente pour l'attaquer un nombre fixe de $x$ fois, ce qui diminue ses points de vie de $x\times ATK$.
- Ensuite, le dragon utilise à répétition sa capacité de régénération, récupérant $p_i$ points de vie à chaque fois. Si ses points de vie valent $0$ avant d'utiliser cette capacité ou après l'une de ces régénérations, le dragon meurt et le joueur franchit ce niveau.
Le nombre d'attaques du robot est donc manifestement essentiel pour terminer le jeu le plus vite possible. 小 D connaît désormais toutes les caractéristiques de chaque dragon et souhaite vous mettre à l'épreuve : à quelle valeur faut-il régler le nombre d'attaques $x$ du robot pour terminer le jeu avec le moins d'attaques possible ?
Bien entendu, si aucune valeur ne permet de terminer le jeu, affichez simplement -1.
Entrée
Lisez les données dans le fichier dragon.in.
La première ligne contient un entier $T$, le nombre de jeux de données.
Les $T$ jeux de données suivent ; chacun comporte 5 lignes.
- La première ligne de chaque jeu de données contient deux entiers $n$ et $m$, le nombre de dragons et le nombre initial d'épées ;
- La ligne suivante contient $n$ entiers positifs : le $i$-ième indique les points de vie initiaux $a_i$ du $i$-ième dragon ;
- La ligne suivante contient $n$ entiers positifs : le $i$-ième indique la capacité de régénération $p_i$ du $i$-ième dragon ;
- La ligne suivante contient $n$ entiers positifs : le $i$-ième indique la puissance d'attaque de l'épée reçue en récompense après avoir tué le $i$-ième dragon ;
- La ligne suivante contient $m$ entiers positifs, les puissances d'attaque des $m$ épées initialement possédées.
Sortie
Écrivez la sortie dans le fichier dragon.out.
La sortie comporte $T$ lignes.
La $i$-ième ligne contient un entier : le nombre minimal d'attaques $x$ permettant au robot de terminer le jeu pour le $i$-ième jeu de données. Si aucune solution n'existe, affichez -1.
Exemples
Entrée 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
Sortie 1
59 -1
Remarque
Premier jeu de données :
- Initialement, les puissances d'attaque des épées sont $\{1,9,10\}$. Le premier dragon possède $3$ points de vie ; l'épée de puissance $1$ est donc choisie. Les $59$ attaques infligent $59$ points de dégâts, ramenant les points de vie du dragon à $-56$. Après $14$ régénérations, ils valent exactement $0$, et le dragon meurt.
- L'épée de puissance $1$ disparaît et une épée de puissance $7$ est ramassée. Les puissances des épées possédées sont alors $\{7,9,10\}$. Le deuxième dragon possède $5$ points de vie ; l'épée de puissance $7$ est donc choisie. Les $59$ attaques infligent $413$ points de dégâts, ramenant ses points de vie à $-408$. Après $68$ régénérations, ils valent exactement $0$, et le dragon meurt.
- Les puissances des épées possédées sont maintenant $\{3,9,10\}$. Le troisième dragon possède $7$ points de vie ; l'épée de puissance $3$ est donc choisie. Les $59$ attaques infligent $177$ points de dégâts, ramenant ses points de vie à $-170$. Après $17$ régénérations, ils valent exactement $0$, et le dragon meurt.
- Aucune solution ne permet de terminer avec moins de $59$ attaques ; la réponse est donc $59$.
Deuxième jeu de données :
- Aucune méthode ne permet de tuer à la fois le premier et le deuxième dragon. Il est donc impossible de terminer le jeu ; affichez
-1.
Exemple 2
Voir les fichiers dragon/dragon2.in et dragon/dragon2.ans dans le répertoire des candidats.
Sous-tâches
| Numéro du test | $n$ | $m$ | $p_i$ | $a_i$ | Puissance d'attaque | Autres restrictions |
|---|---|---|---|---|---|---|
| 1 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | Aucune |
| 2 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | Aucune |
| 3 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | Aucune |
| 4 | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | Aucune |
| 5 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Propriétés 1 et 2 |
| 6 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Propriétés 1 et 2 |
| 7 | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Propriétés 1 et 2 |
| 8 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propriété 1 |
| 9 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propriété 1 |
| 10 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propriété 1 |
| 11 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propriété 1 |
| 12 | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propriété 1 |
| 13 | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | Aucune restriction particulière |
| 14 | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | Aucune restriction particulière |
| 15 | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | Aucune restriction particulière |
| 16 | $\le 10^5$ | $\le 10^5$ | Tous les $p_i$ sont premiers | $\le 10^{12}$ | $\le 10^6$ | Propriété 1 |
| 17 | $\le 10^5$ | $\le 10^5$ | Tous les $p_i$ sont premiers | $\le 10^{12}$ | $\le 10^6$ | Propriété 1 |
| 18 | $\le 10^5$ | $\le 10^5$ | Aucune restriction particulière | $\le 10^{12}$ | $\le 10^6$ | Propriété 1 |
| 19 | $\le 10^5$ | $\le 10^5$ | Aucune restriction particulière | $\le 10^{12}$ | $\le 10^6$ | Propriété 1 |
| 20 | $\le 10^5$ | $\le 10^5$ | Aucune restriction particulière | $\le 10^{12}$ | $\le 10^6$ | Propriété 1 |
Propriété 1 : pour tout $i$, $a_i\le p_i$.
Propriété 2 : $\operatorname{LCM}(p_i)\le 10^6$, c'est-à-dire que le plus petit commun multiple de tous les $p_i$ ne dépasse pas $10^6$.
Pour tous les tests, $T\le 5$, la puissance d'attaque de chaque arme est au plus $10^6$, et le plus petit commun multiple de tous les $p_i$ est au plus $10^{12}$.
Remarque
Les résultats intermédiaires peuvent être très grands ; faites attention au type des variables utilisées pour les stocker.