Задача №111712. Распил брусьев

Вам нужно распилить деревянный брус на несколько кусков. Компания берет плату за пилку в зависимости от размера бруса, который нужно распилить. За разрезание бруса длиной l берется l у.е.

Легко понять, что различные заказы приводят к различным ценам. Найдите минимальную стоимость распила для любого бруса заданного размера.

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

В первой строке число L(1 ≤ L ≤ 1000) — начальная длина бруса, следующая строка содержит число распилов n(1 ≤ n ≤ 160), которые нужно сделать. Следующая строка содержит n положительных чисел (0 ≤ c_i ≤ L) — места, в которых нужно сделать распилы.

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

Выведите минимальную стоимость распила.

Примеры

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

10
3
2 4 7

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

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

100
3
25 50 75

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

Сдать: для сдачи задач необходимо войти в систему