Problem
Na Terra Encantada, são usadas moedas de valores A
1, A
2,..., A
M. O mágico veio à loja e descobriu que tinha exatamente duas moedas de cada valor. Ele precisa pagar a quantia N. Escreva um programa para determinar se ele pode pagar sem troco.
Entrada
Na entrada do programa primeiro vem o número N (1 <= N <= 10
9), depois o número M (1 <= M <= 15) e depois M números distintos aos pares A
1 , A
2,..., A
M (1 <= A
i <= 10
9 ).
Impressão
Primeira impressão K - o número de moedas que o Magic Man terá que dar se puder pagar o valor especificado sem troco. Em seguida, imprima K números que definem os valores das moedas. Se houver várias soluções, imprima a variante em que o Mágico dá o menor número possível de moedas. Se houver várias dessas opções, imprima qualquer uma delas.
Se você não puder ficar sem troco, imprima um único número 0. Se o Mágico não tiver dinheiro suficiente para pagar o valor especificado, imprima um único número -1 (menos um).
| Entrada |
Saída |
100 6
11 20 30 40 11 99
| 3
40 30 30
|