买二送一(Buy Two Get One Free)

题目描述

有 n 本书，其中第 i 本书的价格为 a_i。

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

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

输入格式

• 第一行：单个整数表示 n；
• 第二行：n 个整数表示 a_1, a_2, ..., a_n。

输出格式

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

样例输入 #1

6
1 3 2 4 5 6

样例输出 #1

16

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

数据范围

• 对于 40% 的分数，1 ≤ n ≤ 100；
• 对于 70% 的分数，1 ≤ n ≤ 5000；
• 对于 100% 的分数，1 ≤ n ≤ 100,000，1 ≤ a_i ≤ 30,000。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐。

测试点分布