Problem A: 买二送一

Problem A: 买二送一

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

SubmitProblemListSolved: 9Submit Num: 18StatisticsShowOff!

Description

有 lns="http://www.w3.org/1998/Math/MathML">n 本书，其中第 lns="http://www.w3.org/1998/Math/MathML">i 本书的价格为 lns="http://www.w3.org/1998/Math/MathML">ai。

现有买二送一的购书活动：凡购买两本书，可以免费带走第三本书，但免费书的价格不能超过两本付费书中任意一本。

请问，买下全部的书最少需要多少钱？

  • 对于 lns="http://www.w3.org/1998/Math/MathML">40% 的分数，lns="http://www.w3.org/1998/Math/MathML">1≤n≤100；
  • 对于 lns="http://www.w3.org/1998/Math/MathML">70% 的分数，lns="http://www.w3.org/1998/Math/MathML">1≤n≤5000；
  • 对于 lns="http://www.w3.org/1998/Math/MathML">100% 的分数，lns="http://www.w3.org/1998/Math/MathML">1≤n≤100,000，lns="http://www.w3.org/1998/Math/MathML">1≤ai≤30,000。

Input

  • 第一行：单个整数表示 lns="http://www.w3.org/1998/Math/MathML">n；
  • 第二行：lns="http://www.w3.org/1998/Math/MathML">n 个整数表示 lns="http://www.w3.org/1998/Math/MathML">a1,a2,…,an。

Output

  • 单个整数：表示将所有书买下的最少钱数。

Sample Input Copy 

6
1 3 2 4 5 6

Sample Output Copy 

16

HINT

买2与3，送1；
买5与6，送4。
 

说明：
排序后：5 5 5 5 5
付费：第1、2、4、5本付费（20元）
免费：第3本免费

Submit