La trama fenicia

Estás buscando ganar dinero en un mercado de nicho: La liga de fútbol UPV. Tu esquema es muy simple, a pesar de no tener ni idea de quien va ganar los partidos, te das cuenta de un truco que te permite predecir el resultado del ultimo partido y cobrarle a la gente por ello. La liga consta de $N$ rondas consecutivas, en cada partido, hay $K$ resultados posibles que son equiprobables. Para tu esquema, has diseñado un sistema de confianza: - Consigues una cantidad $E$ de estudiantes iniciales. - Antes de cada partido envías una predicción gratuita a cada uno. - Si la prediccion acierta, el nivel de confianza de esa persona aumenta en $A$ puntos. - Si tu predicción falla, el nivel de confianza de esa persona se desploma a $0$ y te bloquea por la rabia que le has hecho pasar. Tu objetivo para ganar dinero es muy simple: vendes la prediccion final (de la ronda $N$) a aquellas personas cuyo nivel de confianza sea mayor o igual a $U$, las cuales estarán dispuestas a pagar $C$ pesetas por el resultado que los hará millonarios. Quieres garantizar recaudar al menos $P$ pesetas en total, sin importar que resultado tenga cada partido (ya que no tienes ni idea). ¿Cuál es la cantidad mínima de estudiantes $E$ que necesitas de forma inicial para garantizar una ganancia de P pesetas, asumiendo que distribuyes las predicciones de la forma más estrategica posible? ## Entrada La primera línea contiene un entero $T$, el número de casos de prueba. Cada caso de prueba consta de una línea con 6 enteros: $N$, $K$, $P$, $C$, $A$ y $U$, respectivamente. - $N$: Rondas totales (se cobra una antes de la ronda $N$). Está garantizado que $2 \le N \le 20$. - $K$: Resultados posibles por partido. Está garantizado que $2 \le K \le 3$. - $P$: Pesetas totales que quieres recaudar. Se garantiza que $1 \le P \le 10^9$ - $C$: Coste de la predicción final (pesetas por persona). Sabemos que $1 \le C \le P$. - $A$: Aumento de confianza en un estudiante por predicción acertada. Siempre se cumple que $1 \le A \le 1000$. - $U$: Umbral de confianza mínimo que debe tener un estudiante para cobrarle. Se sabe que $1 \le U \le 10^9$. ## Salida Por cada caso de prueba, se debe imprimir una línea con la cantidad mínima de estudiantes iniciales ($E$) para recaudar $P$. Si no es posible recaudar la cantidad de dinero con las condiciones dadas, imprime "$-1$".

3
5 2 1000 500 10 20
3 3 100 50 10 30
10 2 10 10 10 90

8
-1
512