Problem1097--木匠PIPI

1097: 木匠PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 32  Solved: 28
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI现在又成了一名木匠,接一些切木头的活。
顾客会给PIPI一根长度为m的木棍,以及n个需要PIPI切割的点(均为正数)。木棍可以看作一个[0,m]的区间,n个待切割的点都属于这个区间。
但是每次切割都以该切割点所在完整区间长度为代价,所以选择不同的切割顺序将产生不同的代价。
例如一根长为10的木棍,待切割的点为2,4,7。如果以2,4,7的顺序进行切割,那么代价为10(切前为完整的木棍,长度为10)+ 8(切前木棍在2断开成两段,这一段为[2,10],长度为8)+ 6(切前区间为[4,10])=24
如果以4,2,7的顺序切割,那么代价为10+4+6=20.
现在请你帮PIPI制定切割方案以获得最小的代价~输出最小代价即可~

Input

多组数据
第一行为两个整数m,n,1<=m<=1000,0<=n<=50
第二行为N个整数Ai,表示待切割的点,0<Ai<m

Output

对于每组数据,输出一个整数,表示最小代价

Sample Input

100 3
25 50 75
10 4
4 5 7 8

Sample Output

200
22

Source/Category