El mejor ataque combinado
En un juego de cartas similar a Magic se simula una batalla entre dos poderosos magos. Cada carta representa un ataque o hechizo que se puede lanzar al enemigo, y tiene asociado un coste en maná. El maná es la energía del mago, que puede usarse para invocar hechizos. El poder de una carta es igual a su coste en maná. Así, los ataques más poderosos tienen asociado un mayor coste. Sólo es posible jugar una carta si se dispone de la cantidad suficiente de maná.
Además es posible realizar varios ataques a la vez juntando varias cartas en un ataque combinado o combo. Para crear un combo se aplican las siguientes reglas:
- Una carta se puede considerar un combo de tamaño 1, cuyo poder y coste son iguales al maná de la misma.
- Se pueden unir dos combos gastando una cantidad de maná equivalente a la suma de los costes de cada uno de ellos. El poder del combo resultante será igual a la suma de los manás de todas las cartas incluidas.
Por ejemplo, si un jugador tiene en su mano tres cartas con maná 1, 2 y 3 respectivamente, puede hacer las siguientes jugadas:
- Jugar una única carta, con coste/poder 1, 2 o 3.
- Crear un combo de dos cartas, con coste/poder 3 (cartas 1 y 2), 4 (cartas 1 y 3), o 5 (cartas 2 y 3).
- Crear un combo de tres cartas con un poder de 6. El coste en maná de este combo dependerá del orden en que se combinen las cartas:
- Si se añade la carta 3 al combo 1-2, el coste total será 9: el coste de crear el combo 1-2 (3) más el coste de unir el combo 1-2 y la carta 3 (3+3).
- Si se añade la carta 2 al combo 1-3, el coste total será 10: el coste de crear el combo 1-3 (4) más el coste de unir el combo 1-3 y la carta 2 (4+2).
- Si se añade la carta 1 al combo 2-3, el coste total será 11: el coste de crear el combo 2-3 (5) más el coste de unir el combo 2-3 y la carta 1 (5+1).
Obviamente, en el caso de querer combinar las 3 cartas, la opción más barata es combinar primero la 1 y la 2, y luego añadir la 3. Consideraremos siempre que el coste de crear un combo es el menor posible entre todas las opciones.
La pregunta que nos hacemos es, dado un conjunto de cartas y una cantidad de maná disponible, ¿cuál es el ataque más potente que se puede realizar? En el ejemplo anterior, con una cantidad de maná de 6, el mejor ataque que se puede hacer es 5. En cambio con una cantidad de maná de 9 o más se podría hacer un ataque de 6.
Entrada
La entrada está formada por distintos casos de prueba. Cada caso de prueba consta de dos líneas. En la primera línea aparecen dos números enteros M y N. El número M (1 ≤ M ≤ 500) es la cantidad de maná disponible. El número N (1 ≤ N ≤ 15) es el número de cartas. En la segunda línea aparecen N números enteros que representan el valor Vi de cada una de las cartas (1 ≤ Vi ≤ 20, i=1,2,...,N).
El final de la entrada se indica con una línea con un único cero que no se debe procesar.
Salida
Para cada caso de prueba, se escribirá una línea con el valor del mejor ataque que se puede realizar.
Entrada de ejemplo
6 3 1 2 3 10 3 2 1 3 21 5 2 1 3 3 4 0
Salida de ejemplo
5 6 10