描述

你的任务是切割不同长度的铜棒，切割铜棒每次只切一段，成本是根据铜棒的长度而定，不同切割的顺序会有不同的成本。

例如：有一根长10米的铜棒必须在第2、4、7米的地方切割，你可以选择先切2米的地方，然后切4米的地方，最后切7米的地方，这样的选择其成本为$10+8+6=24$。因为第一次切时铜棒长10米，第二次切时铜棒长8米，第三次切时铜棒长6米。但是如果你选择先切4米的地方，然后切2米的地方，最后切7米的地方，其成本为：$10+4+6=20$，显然这种切法就是一个较好的选择。

请找出切割一铜棒所需最小的成本。

输入

每组测试数据3行，第一行有1个整数L（L＜1 000），代表需要切割的铜棒的长度。

第二行有一个整数N（N＜50），代表需要切的次数。

第三行有N个正整数 $c_i(0<c_i<L)$ 代表铜棒需被切割的地方。这N个整数均不相同，且由小到大排列好。

L＝0代表输入结束。

输出

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

样例

输入

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

输出

The minimum cutting is 200.
The minimum cutting is 22.

思路

该题就是dp，就是合并石子的逆过程，但是不知道咋写，求大佬指出