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$行，每行都包含一个所需木板的长度$L_i$ 。

Output

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

Samples

3
8
5
8

34

来源

POJ3253