Problem
Nella Terra Incantata si usano monete di taglio A
1, A
2,..., A
M. L'uomo magico arrivò al negozio e scoprì di avere esattamente due monete di ogni taglio. Deve pagare l'importo N. Scrivi un programma per determinare se può pagare senza resto.
Inserimento
All'ingresso del programma prima viene il numero N (1 <= N <= 10
9), poi il numero M (1 <= M <= 15) e poi M numeri distinti a coppie A
1 , LA
2,..., LA
M (1 <= LA
i <= 10
9 ).
Impressum
Prima stampa K - il numero di monete che il Magic Man dovrà dare se può pagare l'importo specificato senza resto. Quindi stampa K numeri che definiscono i valori delle monete. Se ci sono più soluzioni, stampa la variante in cui l'Uomo Magico dà il minor numero possibile di monete. Se sono disponibili diverse opzioni di questo tipo, stampane una qualsiasi.
Se non puoi fare a meno del resto, stampa un singolo numero 0. Se l'Uomo Magico non ha abbastanza soldi per pagare l'importo specificato, stampa un singolo numero -1 (meno uno).
| Input |
Uscita |
100 6
11 20 30 40 11 99
| 3
40 30 30
|