Problem1456--2016NHOI初中 第一题 购书(1.2)

1456: 2016NHOI初中 第一题 购书(1.2)

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

Description

    书店稿促销优惠活动:“卖 3 本免费 1 本”。即如果你买 3 本书,价格最便宜的那本书就不收钱。如果买很多书, 不同分组优惠的价格可能不同。比如,买 7 本书,价格分别是:10,3,2,4,6,4,9。 如果分组是: (10,3,2),(4,6,4)(9),第一组免费价格 2,第二组免费价格 4,第三组不能免费。
现在,你买了
N 本书,请恰当分组(每组 1 本到 3 本),使得花费最少?

Input

第一行包含 1 个整数 N1≤N≤100000
下面 N 行,每行 1 个整数 Ci 表示一本书的价格。 1≤ Ci ≤ 100000

Output

一个整数,最少付款是多少。

Sample Input Copy

4 
3 2 3 2

Sample Output Copy

8

HINT

样例输入2

6 4 5 5 5 5
样例输出 2
21

Source/Category

排序