题目描述

太空梯需要不同长度的能量棒，你的任务是切割能量棒。切割能量棒的成本是根据能 量棒的长度而定。而且切割能量棒的时候每次只切一段。

很显然的,不同切割的顺序会有不同的成本。例如:有一根长$\red{10}$米的能量棒必须在第 $\red{2}$、$\red{4}$、$\red{7}$米的地方切割。这个时候就有几种选择了。你可以选择先切$\red{2}$米的地方,然后切$\red{4}$ 米的地方,最后切$\red{7}$米的地方。这样的选择其成本为: $\red{10+8+6=24}$。因为第一次切时能 量棒长$\red{10}$米,第二次切时能量棒长$\red{8}$米,第三次切时能量棒长$\red{6}$米。但是如果你选择先切 $\red{4}$米的地方,然后切$\red{2}$米的地方,最后切$\red{7}$米的地方,其成本为: $\red{10+4+6=20}$。这成本就是 一个较好的选择。 请找出切割一能量棒所需最小的成本。

输入格式

每组测试数据$\red{3}$行

第一行有$\red{1}$个整数$\red{L(L<1 000),}$代表需要切割的能量棒的长度。

第二行有一个整数$\red{N(N<50) ,}$代表需要切的次数。

第三行有$\red{N}$个正整数$\red{Ci(0< Ci < L)}$代表能量棒需被切制的地方。这$\red{N}$个整数均不 相同,且由小到大排列好。

$\red{L=0}$代表输入结束。

输出格式

对每一组测试数据,输出最小的切制成本。

样例

输入样例

100
3
25 50 75
10
4
4 5 7 8
0

输出样例

The minimum cutting is 200
The minimum cutting is 22