Перенести все топоры за минимальное количество переходов

Ввод: стандартный ввод

Вывод: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мегабайт

В арсеналы в центрах двух городов привезли новые топоры. К несчастью, орк из клана «Боевые Топоры», которому поручили развоз по двум городам, не умеет ни читать, ни считать, и выгрузил коробки с топорами по принципу «и так сойдёт». Во втором городе коробки принимал умный гоблин, который обнаружил недостачу K топоров. Он уверен, что орк не крал топоры, и он знает, что у этого орка никто не осмелится что-либо красть. Поэтому единственное, что могло произойти - это неправильное распределение топоров по городам.

Гоблин и орк отправились в арсенал первого города, чтобы забрать лишние коробки. Да вот беда, их уже разложили по коробкам, а коробки по N стеллажам, причем в одном стеллаже могут лежать коробки только одинаковой вместимости. Найти именно те топоры, которые выгрузил орк, уже нельзя, да и нести он за раз может только одну коробку. Орк не хочет много раз появляться на глазах у охраны, поэтому ему нужно перенести все топоры за минимальное количество переходов. Орк просит вас помочь ему узнать, какое минимальное количество коробок ему придется перенести, чтобы точно восполнить недостачу в первом арсенале.

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

Первая строка ввода содержит разделенные пробелом числа K (5 ≤ K ≤ 1000000) и N (5 ≤ N ≤ 10000) – количество недостающих топоров и количество стеллажей соответственно. Далее, на следующей строке, следуют N чисел ai (1 ≤ ai ≤ 10000) – вместимость коробок в соответствующем стеллаже. Гарантируется, что всегда можно найти нужное количество топоров.

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

В ответ на задачу выведите единственное число – минимальное количество ходов, которое должен совершить орк.

Примеры

входные данные
выходные данные
8 3
1 5 10
4

9 3
1 6 9
1



Примечание

В первом примере орк делает три перехода за коробками вместимостью 1 и один переход за коробкой вместимостью 5.

0