Бедная Bessie работает в магазине сразу за границей в Slobbovia. Монеты здесь не как в USA, их номиналы меняются каждый день!

Помогите оптимально давать сдачу покупателям Slobbovia: набрать $C$ центов ($1 \le C \le 1000$) монетами $N$ номиналов ($1 \le N \le 10$). Все тесты решаемы данными монетами.

С номиналами 50, 25, 10, 5, 1 оптимальные 93 цента набираются $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$: всего 7 монет.

Насколько это сложно? Последние два теста будут трудными.

Входные данные

Читайте стандартный ввод.

Строка 1: целые $C$ и $N$ через пробел.

Строки $2..N+1$: в каждой одно уникальное целое, доступный номинал.

Выходные данные

Пишите в стандартный вывод.

Строка 1: целое, минимум монет для $C$ центов.

Примеры

Входные данные 1

93 5
25
50
10
1
5

Выходные данные 1

7

Источник: USACO, январь 2007, бронза