99081 - 购书

书店稿促销优惠活动:“卖 3 本免费 1 本”。即如果你买 3 本书,价格最便宜的那本书就不收钱。 如果买很多书,不同分组优惠的价格可能不同。比如,买 7 本书,价格分别是:10,3,2,4,6,4,9。如果分 组是:(10,3,2),(4,6,4)和(9),第一组免费价格 2,第二组免费价格 4,第三组不能免费。

现在,你买了 N 本书,请恰当分组(每组 1 本到 3 本),使得花费最少?

输入

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

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

输出

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

样例

输入

4
3
2
3
2

输出

8

输入

6
6
4
5
5
5
5

输出

21

提示

【数据范围】

50% N≤2000。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题