La povera Bessie lavora in un minimarket appena oltre la frontiera in Slobbovia. Monete diverse da USA, valori che cambiano ogni giorno!

Aiuta a dare resto ottimo ai clienti di Slobbovia: $C$ centesimi ($1 \le C \le 1000$) con $N$ tagli ($1 \le N \le 10$). Tutti i test sono risolvibili con le monete date.

Con 50, 25, 10, 5, 1, il minimo per 93 centesimi è $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$: totale 7 monete.

Quanto può essere difficile? Gli ultimi due test saranno impegnativi.

Input

Leggi standard input.

Riga 1: interi $C$ e $N$ separati da spazio.

Righe $2..N+1$: un intero distinto per riga, valore disponibile.

Output

Scrivi standard output.

Riga 1: un intero, minimo di monete per $C$ centesimi.

Esempi

Input 1

93 5
25
50
10
1
5

Output 1

7

Fonte: USACO gennaio 2007, bronzo