Задача №111712. Распил брусьев
Вам нужно распилить деревянный брус на несколько кусков. Компания берет плату за пилку в зависимости от размера бруса, который нужно распилить. За разрезание бруса длиной l берется l у.е.
Легко понять, что различные заказы приводят к различным ценам. Найдите минимальную стоимость распила для любого бруса заданного размера.
Входные данные
В первой строке число L(1 ≤ L ≤ 1000) — начальная длина бруса, следующая строка содержит число распилов n(1 ≤ n ≤ 160), которые нужно сделать. Следующая строка содержит n положительных чисел (0 ≤ ci ≤ L) — места, в которых нужно сделать распилы.
Выходные данные
Выведите минимальную стоимость распила.
Примеры
Входные данные
10 3 2 4 7
Выходные данные
20
Входные данные
100 3 25 50 75
Выходные данные
200
Сдать: для сдачи задач необходимо войти в систему