Problem2325--4-3 附加 第1题     购书

2325: 4-3 附加 第1题     购书

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 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 本),使得花费最少?

输入格式

第一行包含 1 个整数 N1≤N≤100000

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

输出格式

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

输入/输出例子1

输入:

4  

3 2 3 2

输出:

8

输入/输出例子2

输入:

6

6 4 5 5 5 5

输出:

21

Source/Category