Construyendo dianas
Del juego de los dardos hay muchas variantes. Todas consisten en tirar los dardos a una diana dividida en sectores de diferentes colores o que tienen asociada una puntuación distinta y conseguir cierto objetivo.
Queremos proponer una variante a la liga de dardos local: conseguir sumar cierto valor a partir de las puntuaciones obtenidas con los dardos pero con el menor número de tiros que sea posible. Por ahora tenemos una serie de dianas a las que hemos asignado puntuaciones diferentes a sus sectores y estamos interesados en conocer si ciertos valores pueden ser conseguidos tirando dardos a esas dianas y cuántos dardos como mínimo son necesarios en cada ocasión.
Entrada
En la entrada aparecerán diferentes configuraciones de dianas y objetivos. Cada una ocupa dos líneas. En la primera aparecen dos números: el valor (entre 1 y 500) que hay que conseguir sumar tirando dardos a una diana y el número S de sectores (entre 1 y 50) en los que está dividida la diana. En la segunda línea aparecen, en orden estrictamente creciente, las S puntuaciones asociadas a esos sectores (valores entre 1 y 500).
Salida
Para cada caso se escribirá el menor número de dardos necesarios para conseguir la cantidad, separado por dos puntos de las puntuaciones que permiten conseguir ese valor, ordenadas de mayor a menor y separadas por espacios.
Si hay varias soluciones, se escribirá aquella cuya mayor puntuación sea la más alta; si aún siguen existiendo varias soluciones, aquella cuya segunda mayor puntuación sea la más alta; y así sucesivamente.
Si es imposible conseguir el objetivo con las puntuaciones asignadas a los sectores de la diana, se escribirá Imposible.
Entrada de ejemplo
100 5 10 15 20 25 30 8 3 1 4 6 25 2 8 12
Salida de ejemplo
4: 30 30 30 10 2: 4 4 Imposible