Problem
In einem magischen Land werden Münzen mit dem Wert A
1, A
2, verwendet..., A
M. Der magische Mann kam in den Laden und fand heraus, dass er genau zwei Münzen von jedem Wert hatte. Er muss den Betrag bezahlen. Schreiben Sie ein Programm, das bestimmt, ob er ohne Übergabe bezahlen kann.
Eingabe
Die Nummer N (1 <= N <= 10
9) wird zuerst eingegeben, gefolgt von der Zahl M (1 <= M <= 15) und dann von M paarweise verschiedenen Zahlen A
1, A
2,..., A
M (1 <= A
i <= 10
9).
Ausgabe
Geben Sie zuerst K aus - die Anzahl der Münzen, die dem magischen Mann gegeben werden müssen, wenn er den angegebenen Betrag ohne Einzahlung bezahlen kann. Als nächstes geben Sie die K-Zahlen aus, die die Werte der Münzen angeben. Wenn es mehrere Lösungen gibt, geben Sie die Option aus, in der eine magische Person die kleinste mögliche Anzahl von Münzen gibt. Wenn es mehrere solcher Optionen gibt, geben Sie eine von ihnen aus.
Wenn Sie es nicht tun können, geben Sie eine Zahl 0 aus. Wenn der magische Mann nicht genug Geld hat, um den angegebenen Betrag zu bezahlen, geben Sie eine Zahl -1 (minus eins) aus.
| Eingabe |
Ausgabe |
100 6
11 20 30 40 11 99 |
3
40 30 30 |