提示: 欢迎访问OurACM平台。
Problem 1529 Cutting

Accept: 186    Submit: 530
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

A公司有一台钢管切割机提供钢管加工业务。钢管切割机每次可以将一根钢管按照要求在指定位置切割为2段。每次切割的费用为钢管的长度。

给定一根长度为L的钢管,要求将其在位置l1<l2<...<ln处切割为的n+1段钢管,应如何切割才能使总切割费用最小。

Input

多组测试数据。

每组数据第1行有2个正整数L和n,L表示钢管的长度,n表示切割次数。第2行有n个正整数,表示切割位置l1<l2<...<ln。其中,1≤L≤5000,1≤n≤500。

Output

最小切割总费用

Sample Input

100 3 25 50 75

Sample Output

200

Source

FOJ月赛-2007年9月

Submit  Back  Status  Discuss