Description

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

Format

Input

第1行包含一个整数$N$ ，表示木板的数量。第$2～N +1$行，每行都包含一个所需木板的长度$Li$ 。

Output

一个整数，即进行$N -1$次切割的最低花费。

Samples

3
8
5
8

34

来源

POJ3253