2427. TOKOSHI's Roll Cake Cutting Problem

单点时限: 3.0 sec

内存限制: 256 MB

Mr. Sota Tokoshi decided to give a present to his n girl friends that were results of his girl-hunting. According to his elaborate investigation, every n girls love a roll cake made in ICPC (Innovative Cake and Pie Company). Therefore, he ordered a roll cake with l cm, and cut it into n + 1 pieces, n for girls and one for himself, and wrap them for their present. Mr. Tokosh has got a roll cake of length l cm because his order has not been completely understood by staff unfortunately. So Mr. Tokoshi orderd to cut it into n + 1 pieces again. However, ICPC charges money for a cutting operation according to the length of the roll cake being. Moreover, a cutting operation only make one cut at a time. Therefore, different selections in the order of cutting operation may lead to different price. For example, let us consider a roll cake of length 10cm that has to be cut at 1cm, 5cm and 8cm from one end. In case of cutting first at 1cm, then at 5cm, and then at 8cm, a price for these cutting operations is 24 because the first roll cake is of 10cm, the resulting of 9cm, and the last one 5cm. In another case of cutting first at 5cm, then at 1cm, and then at 8 cm, a price is 20 because the first roll cake is cut into two roll cakes of 5cm, and other cutting operations cut these roll cakes. This is an example in the sample input.

Your job is to write a program to calculate the minimum cost of these cutting operations.

输入格式

Input consists of multiple test cases. The first line of each test case contains two positive integers n and l ( n <= 100、n < l < 10,000 ). The next line contains n positive integers indicating the places where the cuts have to be done. You can assume that every cut is done at different place. Input is terminated by a case of n = l = 0, and it should not be processed.

输出格式

For each test case, you should output the minimum cost in a line.

样例

Input
3 10
1 5 8
0 0
Output
20

2 人解决,6 人已尝试。

2 份提交通过,共有 21 份提交。

9.5 EMB 奖励。

创建: 12 年,10 月前.

修改: 4 年前.

最后提交: 9 月,4 周前.

来源: International Maximum-Cup 2008

题目标签