Разрезание палки

Вы должны разрезать деревянную палку на куски. Самая доступная компания 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$ положительных чисел $c_i(0<c_i<l)$, представляющих места для разрезов, заданные в строго возрастающем порядке. Строка с $l=0$ обозначает конец входных данных.

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

Выведите минимальную стоимость разрезания палки в формате, приведенном в примере.

Примеры