Die arme Bessie arbeitet in einem Convenience-Store direkt hinter der Grenze in Slobbovia. Die Münzen sind anders als in den USA, ihre Werte ändern sich täglich!

Hilf beim optimalen Wechselgeld für Kunden von Slobbovia: $C$ Cent ($1 \le C \le 1000$) mit $N$ Münzwerten ($1 \le N \le 10$). Alle Tests sind mit den gegebenen Münzen lösbar.

Mit 50, 25, 10, 5, 1 wären 93 Cent optimal mit $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$, insgesamt minimal 7 Münzen.

Wie schwer kann es sein? Die letzten beiden Tests werden schwierig.

Eingabe

Lies Standardeingabe.

Zeile 1: ganze Zahlen $C$ und $N$ mit Leerzeichen.

Zeilen $2..N+1$: je eine eindeutige ganze Zahl als nutzbarer Münzwert.

Ausgabe

Schreibe Standardausgabe.

Zeile 1: eine ganze Zahl, minimale Münzen für $C$ Cent.

Beispiele

Eingabe 1

93 5
25
50
10
1
5

Ausgabe 1

7

Quelle: USACO Januar 2007, Bronze