Cutting a stick

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. Their 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 $10$ meters that needs to be cut at $2$, $4$, and $7$ meters from one end. Consider a few options:

• You could cut first at $2$ meters, then at $4$ meters, and finally at $7$ meters. This would result in a cost of $10+8+6=24$, because the first piece was $10$ meters, the second $8$ meters, and the third $6$ meters.

• In another option, if you first cut at $4$ meters, then at $2$ meters, and finally at $7$ 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.

Input

Consist 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 $n$ 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.

Output

Print the minimal cost of cutting the stick in the format given in the example.

Examples