Problem1806--打包货物

1806: 打包货物

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

物流公司要发送一批货物,发送之前要对货物进行包装,现在有 N 种货物,发送第 i 种货物的价格 是 Price[i]。物流公司有个规定,如果把任意的 3 种货物放在一起打包,那么这 3 种货物之中价格最低的 那种货物可以不用给钱。那么,为了节约成本,应该如何打包,才能用最少的钱把这 N 种货物打包好?注 意:最多 3 种货物一起打包,你不能尝试着把 4 种货物放在一起打包。

Input

第一行,一个整数 N。 1<=N<=2000。 
接下来有 N 行,第 i 行是一个整数,表示发送第 i 种的价钱 Price[i]。 1<=Price[i]<=100000。 

Output

一个整数,最少的钱。

Sample Input Copy

4
3
2
3
2

Sample Output Copy

8

HINT



Source/Category

排序