切割能量棒

成绩 100 开启时间 2016年05月30日 星期一 20:15
折扣 0.8 折扣时间 2016年05月30日 星期一 20:15
允许迟交 是 关闭时间 2016年05月30日 星期一 20:15
输入文件 CuttingSticks.in 输出文件 CuttingSticks.out

【题目描述】切割能量棒(CuttingSticks.cpp/c/pas)  uva10003

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

很显然的，不同切割的顺序会有不同的成本。例如：有一根长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<1000），代表需要切割的能量棒的长度。

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

第三行有N个正整数Ci（0 < Ci < 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.