Uno de nuestros mejores amigos se va a casar y todos estamos nerviosos porque es el primero de nosotros en hacer algo similar. De hecho, nunca hemos asistido a una boda, por lo que no tenemos ropa ni accesorios. Para solucionar el problema, vamos a un famoso centro comercial de nuestra ciudad a comprar todo lo que necesitamos: una camisa, un cinturón, unos zapatos, una corbata, etc.

Nos ofrecen diferentes modelos para cada tipo de prenda (por ejemplo, tres camisas, dos cinturones, cuatro pares de zapatos, ...). Tenemos que comprar un modelo de cada tipo de prenda, y solo uno. Como nuestro presupuesto es limitado, no podemos gastar más dinero del que tenemos, pero queremos gastar la mayor cantidad posible. Es posible que no podamos comprar un modelo de cada tipo de prenda debido a la poca cantidad de dinero que tenemos.

La primera línea de la entrada contiene un número entero, N, que indica la cantidad de casos de prueba. Para cada caso de prueba, en la primera línea se encuentran dos enteros, M y C, separados por un espacio (1 ≤ M ≤ 200, y 1 ≤ C ≤ 20), donde M es la cantidad de dinero disponible y C es el número de prendas que debes comprar. En la siguiente línea hay C líneas, cada una comenzando con un número entero K (1 ≤ K ≤ 20), que indica la cantidad de modelos diferentes para cada prenda, seguido de K enteros que indican el precio de cada modelo de esa prenda.

Para cada caso de prueba, la salida debe consistir en un número entero que indique la cantidad máxima de dinero que se puede gastar al comprar un modelo de cada tipo de prenda sin exceder el monto inicial de dinero. Si no es posible, debes imprimir "no tiene solucion".