Biedna Bessie pracuje w sklepie osiedlowym zaraz za granicą w Slobbovia. Monety różnią się od USA, a nominały zmieniają codziennie!

Pomóż optymalnie wydać resztę kupującym Slobbovia: $C$ centów ($1 \le C \le 1000$) z $N$ nominałów ($1 \le N \le 10$). Wszystkie testy są rozwiązywalne danymi monetami.

Z wartościami 50, 25, 10, 5, 1 minimum dla 93 centów to $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$: razem 7 monet.

Jak trudne może to być? Dwa ostatnie testy będą wyzwaniem.

Wejście

Czytaj standardowe wejście.

Wiersz 1: całkowite $C$ i $N$ oddzielone spacją.

Wiersze $2..N+1$: po jednej różnej całkowitej, dostępny nominał.

Wyjście

Pisz standardowe wyjście.

Wiersz 1: liczba całkowita, minimum monet dla $C$ centów.

Przykład

Wejście 1

93 5
25
50
10
1
5

Wyjście 1

7

Źródło: USACO styczeń 2007, brąz