Pauvre Bessie travaille dans une supérette juste après la frontière en Slobbovia. Les pièces diffèrent de celles utilisées aux USA et les valeurs changent chaque jour !

Aidez-la à rendre la monnaie optimale aux clients de Slobbovia : $C$ cents ($1 \le C \le 1000$) avec $N$ valeurs de pièces ($1 \le N \le 10$). Tous les tests sont réalisables avec les pièces données.

Avec 50, 25, 10, 5, 1, les 93 cents optimaux (minimum de pièces) utilisent $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$, soit 7 pièces.

Est-ce si difficile ? Les deux derniers tests seront exigeants.

Entrée

Lisez l’entrée standard.

Ligne 1 : entiers $C$ et $N$ séparés par un espace.

Lignes $2..N+1$ : un entier distinct par ligne, valeur d’une pièce utilisable.

Sortie

Écrivez sur la sortie standard.

Ligne 1 : un entier, le minimum de pièces pour $C$ cents.

Exemples

Entrée 1

93 5
25
50
10
1
5

Sortie 1

7

Source : USACO janvier 2007, bronze