练习专区

一个人要把一根木头分成N块。但是这个人自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。请编写程序帮助农夫计算将木头锯成N块的最少花费。

输入有若干个案例。第一行是一个正整数N，表示要将木头分成N块。第二行是N个正整数，表示切割后每段木头的长度。

将木头分成N块的最少花费。

5
1 3 4 5 6
8
30 20 15 10 10 5 5 5
8
4 5 1 2 1 3 1 1
1
1

42
275
49
0