A pobre Bessie trabalha numa loja de conveniência logo além da fronteira em Slobbovia. Suas moedas diferem das usadas nos USA e os valores mudam todo dia!

Ajude a dar troco ótimo aos clientes de Slobbovia: $C$ centavos ($1 \le C \le 1000$) com $N$ valores de moedas ($1 \le N \le 10$). Todos os testes são solucionáveis com as moedas dadas.

Com 50, 25, 10, 5, 1, o troco ótimo mínimo de 93 centavos usa $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$: total 7 moedas.

Quão difícil pode ser? Os dois últimos testes serão desafiadores.

Entrada

Leia entrada padrão.

Linha 1: inteiros $C$ e $N$ separados por espaço.

Linhas $2..N+1$: um inteiro distinto por linha, valor disponível.

Saída

Escreva saída padrão.

Linha 1: um inteiro, mínimo de moedas para $C$ centavos.

Exemplos

Entrada 1

93 5
25
50
10
1
5

Saída 1

7

Fonte: USACO janeiro de 2007, bronze