Copiado al portapapeles
Descripción
¿Quién no comió helado alguna vez?, si no lo hiciste no sabes de lo que te pierdes.
José es un muchacho que ama los helados y siempre soñó con comer helado todo el día, por suerte él fue ahorrando dinero para poder ir al gran Palacio de los helados y comer todo el helado que pueda.
El palacio de los helados cuenta con infinidad de sabores como Chocolate, Vainilla, Fresa, Naranja, etc. y cada sabor viene en diferentes porciones y un precio. Por ejemplo podemos encontrar el sabor de chocolate en 3 porciones diferentes a 10Bs, 15Bs y 25Bs respectivamente.
José al llegar al palacio de los helados y ver los precios notó que no cuenta con suficiente dinero para poder comprar todo el helado que hay. Entonces el estará conforme con probar un helado de cada sabor.
Él quiere comer todos los sabores que hay y no sabe si el dinero le va a alcanzar. Así que pide tu ayuda. Él quiere gastar el máximo monto de dinero posible con la condición de probar todos los sabores que hay.
Entrada
La primera línea contiene un entero $N$, indicando el número de casos de prueba que hay. Para cada caso de prueba la primera línea tendrá 2 enteros $M$ y $C$. separados por un espacio en blanco $(1 \leq M \leq 200)$, y $(1 \leq C \leq 20)$, donde $M$ es la cantidad de dinero que pudo ahorrar José y $C$ es la cantidad de sabores que hay.
Seguidamente existirá $C$ líneas, de cada una de estas líneas te darán un entero $K (1 \leq K \leq 20)$, indicando el número de porciones del sabor que hay, seguido por $K$ enteros indicando el precio de la porción del sabor $C_i$.
Salida
Para cada caso de prueba debe imprimir el máximo monto de dinero que José gasto en probar todos los sabores de helados (claro sin exceder este monto). Si no es posible probar todos los sabores que hay, debes imprimir “No es posible”.
Ejemplo Entrada
3 100 4 3 8 6 4 2 5 10 4 1 3 3 7 4 50 14 23 8 20 3 3 4 6 8 2 5 10 4 1 3 5 5 5 3 3 6 4 8 2 10 6 4 7 3 1 7
Ejemplo Salida
75 19 No es posible
Ayuda
2da div. 2012 UMSA