Cutting a stick#11261
You need to cut a wooden stick into pieces. The most affordable company, The Analog Cutting Machinery, Inc. (ACM), charges money based on the length of the stick being cut. The procedure requires making only one cut at a time.
It is easy to see that different choices of the cutting order lead to different costs. For example, consider a stick of length meters that needs to be cut at , , and meters from one end. Consider a few options:
You could cut first at meters, then at meters, and finally at meters. This would result in a cost of 10 + 8 + 6 = 24, because the first piece was meters, the second meters, and the third meters.
In another option, if you first cut at meters, then at meters, and finally at meters, the cost would be 10 + 4 + 6 = 20, which is the better price.
Your boss trusts your computing skills to determine the minimal cost of cutting the given stick.
Consists of several test cases. The first line of each test case contains the length of the stick l~(l < 1000) that needs to be cut. The next line contains the number of cuts n~(n < 50) to be made.
The following line contains positive integers c_i~(0 < c_i < l), representing the positions for the cuts, given in strictly increasing order. A line with l = 0 denotes the end of the input data.
Print the minimal cost of cutting the stick in the exact format given in the example.
Example 1