La pobre Bessie trabaja en tienda de conveniencia justo tras la frontera en Slobbovia. Usan monedas distintas a USA, ¡con valores que cambian cada día!

Ayuda a dar cambio óptimo a clientes de Slobbovia: $C$ centavos ($1 \le C \le 1000$) con $N$ denominaciones ($1 \le N \le 10$). Todos los tests pueden resolverse con monedas dadas.

Con valores 50, 25, 10, 5, 1, el cambio óptimo mínimo de 93 centavos usa $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$: total 7 monedas.

¿Qué tan difícil será? Los dos últimos tests serán un reto.

Entrada

Lee entrada estándar.

Línea 1: enteros $C$ y $N$ separados por espacio.

Líneas $2..N+1$: un entero único por línea, valor disponible.

Salida

Escribe salida estándar.

Línea 1: un entero, monedas mínimas para $C$ centavos.

Ejemplos

Entrada 1

93 5
25
50
10
1
5

Salida 1

7

Fuente: USACO enero 2007, bronce