monedas
Problem
En la Tierra Encantada se utilizan monedas de denominaciones A1, A2,..., AM. El mago llegó a la tienda y descubrió que tenía exactamente dos monedas de cada denominación. Necesita pagar la cantidad N. Escriba un programa para determinar si puede pagar sin cambio.
Entrada
A la entrada del programa primero viene el número N (1 <= N <= 109), luego el número M (1 <= M <= 15) y luego M números distintos por pares A 1 , A2,..., AM (1 <= Ai <= 10 9).
Impresión
Primero imprima K: la cantidad de monedas que el Hombre Mágico tendrá que dar si puede pagar la cantidad especificada sin cambio. Luego imprime K números que definen los valores de las monedas. Si hay varias soluciones, imprime la variante en la que el Hombre Mágico da el menor número de monedas posible. Si hay varias de estas opciones, imprima cualquiera de ellas.
Si no puede prescindir del cambio, imprima un solo número 0. Si el Hombre Mágico no tiene suficiente dinero para pagar la cantidad especificada, imprima un solo número -1 (menos uno).
| Entrada |
Salida |
100 6
11 20 30 40 11 99
| 3
40 30 30
|