Вы должны разрезать деревянную палку на куски. Самая доступная компания The Analog Cutting Machinery, Inc. (ACM) взимает плату в зависимости от длины разрезаемой палки. Их порядок работы требует совершать только один разрез за раз.
Легко заметить, что разный выбор порядка разреза приводит к разным ценам. Например, рассмотрим палку длиной метров, которую следует разрезать в точках и метров с одного конца. Рассмотрим несколько вариантов. Можно резать сначала в , затем в , затем в . Это приведет к цене , потому что первая палка была метров, вторая , а третья . В другом варианте сначала разрежем в , затем в , а затем в . Это приведет к цене , что является лучшей ценой.
Ваш начальник доверяет Вашим компьютерным способностям определить минимальную стоимость разрезания данной палки.
Состоит из нескольких тестов. Первая строка каждого теста содержит длину палки , которую следует разрезать. Следующая строка содержит количество разрезов, которое необходимо сделать.
Следующая строка состоит из положительных чисел , представляющих места, где необходимо выполнить разрезы, заданные в строго возрастающем порядке. Строка с представляет конец входных данных.
Выведите минимальную стоимость разрезания данной палки в формате, приведенном в примере.