#2478. 围栏修复

围栏修复

Description

约翰想修牧场周围的篱笆,需要NN1N20000(1≤N ≤20000)木板,每块木板的长度都为LiLi 1Li500001≤Li ≤50000,整数)米。他购买了一块足够长的木板(长度为LiLi 的总和,i=1,2,,Ni =1, 2,…, N ),以便得到NN 块木板,切割时木屑损失的长度不计。唐向约翰收取切割费用,切割一块木板的费用与其长度相同,切割2121米的木板需要2121美分。唐让约翰决定切割木板的顺序和位置。约翰知道以不同的顺序切割木板,将会产生不同的费用。请帮助约翰确定他得到N 块木板的最低花费。

Format

Input

第1行包含整数NN ,表示木板的数量。

2..N+12..N +1行,每行都包含一个所需木板的长度LiL_i

Output

一个整数,即进行N1N -1次切割的最低花费。

Samples

3
8
5
8
34

来源

POJ3253