Problem
Dans le pays enchanté, des pièces de monnaie de dénominations A
1, A
2,..., A
M sont utilisées. L'homme magique est venu au magasin et a découvert qu'il avait exactement deux pièces de chaque dénomination. Il doit payer le montant N. Écrivez un programme pour déterminer s'il peut payer sans monnaie.
Entrée
A l'entrée du programme vient d'abord le nombre N (1 <= N <= 10
9), puis le nombre M (1 <= M <= 15) puis M nombres distincts deux à deux A
1 , A
2,..., A
M (1 <= A
i <= 10
9).
Mentions légales
Imprimez d'abord K - le nombre de pièces que le Magic Man devra donner s'il peut payer le montant spécifié sans changement. Puis imprimez les nombres K qui définissent les valeurs des pièces. S'il y a plusieurs solutions, imprimez la variante dans laquelle le Magic Man donne le plus petit nombre de pièces possible. S'il existe plusieurs options de ce type, imprimez-en une.
Si vous ne pouvez pas vous passer de monnaie, imprimez un seul chiffre 0. Si le Magic Man n'a pas assez d'argent pour payer le montant spécifié, imprimez un seul chiffre -1 (moins un).
| Entrée |
Sortie |
100 6
11 20 30 40 11 99
| 3
40 30 30
|