Вы должны разрезать деревянную палку на куски. Самая доступная компания The Analog Cutting Machinery, Inc. (ACM) взимает плату в зависимости от длины разрезаемой палки. Их порядок работы требует совершать только один разрез за раз.
Легко заметить, что разный выбор порядка разреза приводит к разным ценам. Например, рассмотрим палку длиной 10 метров, которую следует разрезать в точках 2,4 и 7 метров с одного конца. Рассмотрим несколько вариантов. Можно резать сначала в 2, затем в 4, затем в 7. Это приведет к цене 10+8+6=24, потому что первая палка была 10 метров, вторая 8, а третья 6. В другом варианте сначала разрежем в 4, затем в 2, а затем в 7. Это приведет к цене 10+4+6=20, что является лучшей ценой.
Ваш начальник доверяет Вашим компьютерным способностям определить минимальную стоимость разрезания данной палки.
Состоит из нескольких тестов. Первая строка каждого теста содержит длину палки l (l<1000), которую следует разрезать. Следующая строка содержит количество n (n<50) разрезов, которое необходимо сделать.
Следующая строка состоит из n положительных чисел ci (0<ci<l), представляющих места, где необходимо выполнить разрезы, заданные в строго возрастающем порядке. Строка с l=0 представляет конец входных данных.
Выведите минимальную стоимость разрезания данной палки в формате, приведенном в примере.