单点时限: 2.0 sec
内存限制: 256 MB
约翰正在修复农场的一段围栏。进过丈量，他需要 $N$ 块木板，第 $i$ 块木板的长度应该是 $L_i$。他订购了一根很长的木料，长度就是这 $N$ 块木板的总长度，由于约翰没有锯子，所以他找到了老唐，想让他帮忙锯开木料。
老唐是个生意精，他乐意代劳，但劳动不是无偿的。每开动一次锯子，可以把木料锯成两段，锯出 $N$ 块木板就需要开动 $N − 1$ 次机器。老唐说，每次开机都要收加工费，加工费用正比于需要锯开的木料长度。比如要把一段长 20 米的木料锯开，就要收 20 元。约翰不得不接受了老唐的要求，但他发现不同的切割次序会产生不同的费用。请帮约翰设计一个锯开木料的方案，使得约翰付出的加工费之和最小。
第一行：单个整数 $N$，$1 \leq N \leq 20000$
第二行到第 $N + 1$ 行：第 $i + 1$ 行有一个整数 $L_i$，$1 \leq L_i \leq 50000$
单个整数：表示约翰付出的最小费用
3 8 5 8
34