2-5 修理牧场(35分)

农夫计划对牧场某处的栅栏进行维修。随后对这一区域的栅栏进行了测量后发现共需采购N块木材。每根木材的长度均为整数值L_i（单位：个长度单位）。为了实现这一目标农夫采购了一根足够长且可分割成N段的木材其总长度等于各木材长度之和。

但是农夫自身不具备锯子这一工具，请人代为切割木材时所支付的费用与其被切割段落的长度呈正比关系。为了便于分析问题，在此假设切割费用等于被切割木材段落的实际长度值。举例而言，在处理一根长度为20单位木材时将其分割成长度分别为8、7和5三个部分：第一次切割耗费的成本是20单位并将其分为12和8两部分；随后第二次切割则在剩下的12单位木材上投入成本12单位并将其分为7和5两个较小的部分；两次切割总共产生的费用合计32单位。如果在第一次切割时采用不同的分法即将木材分割成长15和5两个部分，则第二次切割所需的成本将是15单位导致总费用升至35单位（高于之前的32单位）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

输入格式:

程序开始时读取一个正整数N，并规定其最大值为104。目的是将其分割成恰好N段。接下来一行包含N个不超过50的正整数。

输出格式:

输出一个整数，即将木头锯成N块的最少花费。

输入样例:

    8
    4 5 1 2 1 3 1 1

输出样例:

    49
``