El ingeniero Luis ha quedado varado en un planeta lleno de basura. Como buen ambientalista, quiere reciclar todos los materiales disponibles para construir objetos útiles y así volver a su planeta natal. Luis cuenta con ~N~ tipos de recicladoras. La recicladora tipo ~i~ produce ~p_i~ unidades por segundo del material ~i~. Existen ~M~ tipos de objetos que se pueden ensamblar. Para el objeto tipo ~j~ se tiene:

• Requiere ~k_j~ materiales diferentes ~(1 \leq k_j \leq 4)~.
• Tarda ~t_j~ segundos en producirse.
• Necesita ~q_1, q_2,..., q_{k_j}~ unidades de los materiales ~b_1, b_2,..., b_{k_j}~ respectivamente.

Luis puede construir ensambladoras. Cada ensambladora se dedica a un solo tipo de objeto y produce un objeto cada ~t_j~ segundos, consumiendo los materiales requeridos.

Tu tarea es determinar la cantidad mínima de ensambladoras que Luis debe construir para que el sistema esté en equilibrio perfecto, es decir, que todo el material producido por las recicladoras sea consumido exactamente por las ensambladoras. Si es imposible lograr este equilibrio, imprime -1.

Entrada

La primera línea contiene un entero ~T~ ~(1 \leq T \leq 100)~, el número de casos de prueba.

Cada caso de prueba contiene:

• Una línea con dos enteros ~N~ y ~M~ ~(1 \leq N \leq 4, 1 \leq M \leq 5)~.
• Una línea con ~N~ enteros ~p_1, p_2,..., p_N~ ~(1 \leq p_i \leq 10^5)~.
• ~M~ bloques, uno por objeto. Cada bloque:
• Una línea con ~k_j~ y ~t_j~ ~(1 \leq k_j \leq 4, 1 \leq t_j \leq 20)~.
• Una línea con ~k_j~ enteros ~b_1,..., b_{k_j}~ ~(1 \leq b_i \leq N)~, los materiales requeridos.
• Una línea con ~k_j~ enteros ~q_1,..., q_{k_j}~ ~(1 \leq q_i \leq 200)~, las cantidades necesarias.

Salida

Para cada caso de prueba, imprime un entero: la mínima cantidad de ensambladoras necesarias, ó -1 si es imposible.

Ejemplo de Entrada

3
2 1
6 8
2 2
1 2
3 4
1 2
30
1 5
1
2
1 3
1
10
2 1
5 7
2 1
1 2
2 4

Ejemplo de Salida

4
9
-1