小 D ha descubierto recientemente un pequeño juego en Internet. Sus reglas son las siguientes:
- El objetivo es matar $n$ dragones en el orden de sus números, de $1$ a $n$. Cada dragón tiene una vida inicial $a_i$ y una capacidad de recuperación: cuando la utiliza, su vida aumenta en $p_i$ cada vez hasta dejar de ser negativa. Solo muere después de terminar los ataques y cuando su vida es exactamente $0$.
- Al empezar, el jugador tiene $m$ espadas cuyas fuerzas de ataque se conocen. Frente a cada dragón solo puede elegir una espada. Al matar al dragón, esa espada desaparece, pero el jugador recibe una espada nueva como recompensa.
小 D encuentra el juego muy aburrido, pero el jugador que lo complete más rápido puede obtener una plaza para participar en ION2018. Por ello decide escribir un robot un poco torpe que lo complete por ella. Su robot sigue estas reglas:
- Frente a cada dragón, el robot elige, entre las espadas que posee cuya fuerza de ataque no supera la vida inicial del dragón, la de mayor fuerza de ataque. Si no existe ninguna, elige la de menor fuerza de ataque.
- Frente a cada dragón, utiliza la espada elegida para atacarlo un número fijo de veces $x$, reduciendo su vida en $x\times ATK$.
- Después, el dragón utiliza repetidamente su capacidad de recuperación, recuperando $p_i$ de vida cada vez. Si su vida es $0$ antes de recuperarse o después de alguna recuperación, muere y el jugador supera esa fase.
Evidentemente, el número de ataques del robot es la clave para completar el juego lo más rápido posible. 小 D ya conoce todos los atributos de los dragones y quiere ponerte a prueba: ¿qué valor debe asignar al número de ataques $x$ para completar el juego con el menor número de ataques posible?
Si no se puede completar el juego con ningún valor, imprime -1.
Entrada
Lee los datos del archivo dragon.in.
La primera línea contiene un entero $T$, que indica el número de conjuntos de datos.
A continuación se dan $T$ conjuntos de datos, cada uno formado por 5 líneas:
- La primera línea contiene dos enteros $n,m$, que indican el número de dragones y el número inicial de espadas, respectivamente.
- La siguiente línea contiene $n$ enteros positivos. El número $i$ es la vida inicial $a_i$ del dragón $i$.
- La siguiente línea contiene $n$ enteros positivos. El número $i$ es la capacidad de recuperación $p_i$ del dragón $i$.
- La siguiente línea contiene $n$ enteros positivos. El número $i$ es la fuerza de ataque de la espada recibida al matar al dragón $i$.
- La siguiente línea contiene $m$ enteros positivos: las fuerzas de ataque de las $m$ espadas iniciales.
Salida
Escribe la salida en el archivo dragon.out.
La salida contiene $T$ líneas.
La línea $i$ contiene un entero: el menor número de ataques $x$ que permite al robot completar el juego para el conjunto de datos $i$. Si no existe respuesta, imprime -1.
Ejemplos
Entrada 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
Salida 1
59 -1
Nota
Primer conjunto de datos:
- Al empezar, las fuerzas de ataque de las espadas son $\{1,9,10\}$. El primer dragón tiene $3$ de vida, así que se elige la espada de fuerza $1$. Se le ataca 59 veces y se le causan $59$ puntos de daño, dejando su vida en $-56$. Tras recuperarse 14 veces, su vida es exactamente $0$ y muere.
- La espada de fuerza $1$ desaparece y se recoge una de fuerza $7$. Ahora las fuerzas son $\{7,9,10\}$. El segundo dragón tiene $5$ de vida, así que se elige la espada de fuerza $7$. Se le ataca 59 veces y se le causan $413$ puntos de daño, dejando su vida en $-408$. Tras recuperarse 68 veces, su vida es exactamente $0$ y muere.
- Ahora las fuerzas de las espadas son $\{3,9,10\}$. El tercer dragón tiene $7$ de vida, así que se elige la espada de fuerza $3$. Se le ataca 59 veces y se le causan $177$ puntos de daño, dejando su vida en $-170$. Tras recuperarse 17 veces, su vida es exactamente $0$ y muere.
- No existe una forma de completar el juego con menos de 59 ataques, por lo que la respuesta es 59.
Segundo conjunto de datos:
- No existe una forma de matar tanto al primer dragón como al segundo, por lo que no se puede completar el juego y la salida es
-1.
Ejemplo 2
Consulta los archivos dragon/dragon2.in y dragon/dragon2.ans del directorio del concursante.
Subtareas
| Caso de prueba | $n$ | $m$ | $p_i$ | $a_i$ | Fuerza de ataque | Otras restricciones |
|---|---|---|---|---|---|---|
| $1$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | Ninguna |
| $2$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | Ninguna |
| $3$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | Ninguna |
| $4$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | Ninguna |
| $5$ | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Propiedades 1 y 2 |
| $6$ | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Propiedades 1 y 2 |
| $7$ | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^6$ | Propiedades 1 y 2 |
| $8$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propiedad 1 |
| $9$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propiedad 1 |
| $10$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propiedad 1 |
| $11$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propiedad 1 |
| $12$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propiedad 1 |
| $13$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | Propiedad 1 |
| $14$ | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | Sin restricciones especiales |
| $15$ | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | Sin restricciones especiales |
| $16$ | $\le 10^5$ | $\le 10^5$ | Todos los $p_i$ son primos | $\le 10^{12}$ | $\le 10^6$ | Propiedad 1 |
| $17$ | $\le 10^5$ | $\le 10^5$ | Todos los $p_i$ son primos | $\le 10^{12}$ | $\le 10^6$ | Propiedad 1 |
| $18$ | $\le 10^5$ | $\le 10^5$ | Sin restricciones especiales | $\le 10^{12}$ | $\le 10^6$ | Propiedad 1 |
| $19$ | $\le 10^5$ | $\le 10^5$ | Sin restricciones especiales | $\le 10^{12}$ | $\le 10^6$ | Propiedad 1 |
| $20$ | $\le 10^5$ | $\le 10^5$ | Sin restricciones especiales | $\le 10^{12}$ | $\le 10^6$ | Propiedad 1 |
La propiedad 1 significa que, para todo $i$, se cumple $a_i\le p_i$.
La propiedad 2 significa que $\operatorname{LCM}(p_i)\le 10^6$, es decir, que el mínimo común múltiplo de todos los $p_i$ no supera $10^6$.
Para todos los casos de prueba, $T\le 5$, la fuerza de ataque de todas las armas es como máximo $10^6$ y el mínimo común múltiplo de todos los $p_i$ es como máximo $10^{12}$.
Nota
Los resultados intermedios pueden ser muy grandes. Presta atención al tipo de las variables que utilices para almacenarlos.