Q10003: Cutting Sticks

你的任務是替一家叫Analog Cutting Machinery (ACM)的公司切割木棍。切割木棍的成本是根據木棍的長度而定。而且切割木棍的時候每次只切一段。

很顯然的,不同切割的順序會有不同的成本。例如:有一根長10公尺的木棍必須在第2、4、7公尺的地方切割。這個時候就有幾種選擇了。你可以選擇先切2公尺的地方,然後切4公尺的地方,最後切7公尺的地方。這樣的選擇其成本為:10+8+6=24。因為第一次切時木棍長10公尺,第二次切時木棍長8公尺,第三次切時木棍長6公尺。但是如果你選擇先切4公尺的地方,然後切2公尺的地方,最後切7公尺的地方,其成本為:10+4+6=20,這成本就是一個較好的選擇。

你的老闆相信你的電腦能力一定可以找出切割一木棍所需最小的成本。

Input

每組測試資料3列,第一列有1個整數L(L<1000),代表需要切割的木棍的長度。第二列有一個整數N(N<50),代表需要切的次數。第三列有N個正整數Ci(0 < Ci < L)代表木棍需被切割的地方。這N個整數均不相同,且由小到大排列好。

L=0代表輸入結束。請參考Sample Input。

Output

對每一組測試資料,輸出最小的切割成本。請參考Sample Output。

Sample Input

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

Sample Output

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