该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

书店开展“买 3 本免费 1 本”促销活动，具体规则如下：

• 若将书籍分为每组 3 本，则该组中价格最低的 1 本书免费（无需支付该本书的费用）；
• 若购买多本书，可自由将其分成若干组，每组数量可为 1 本、2 本或 3 本（每组数量不超过 3 本）；
• 不同分组方式对应的总免费金额不同，最终总花费 = 所有书籍总价 - 总免费金额。

例如：购买 7 本书，价格分别为 10、3、2、4、6、4、9。若分组为 (10, 3, 2)、(4, 6, 4)、(9)，则：

• 第一组免费最低价 2，第二组免费最低价 4，第三组（1 本）无免费；
• 总免费金额 = 2 + 4 = 6，总花费 = (10+3+2+4+6+4+9) - 6 = 38 - 6 = 32。

现在你购买了 N 本书，每本书价格为 Ci，请设计最优分组方案（每组 1~3 本），使得最终需要支付的总金额最少。

输入格式

1. 第一行包含 1 个整数 N（1 ≤ N ≤ 100000），表示购买的书的数量。
2. 接下来 N 行，每行包含 1 个整数 Ci（1 ≤ Ci ≤ 100000），表示第 i 本书的价格。

输出格式

输出一个整数，表示按照最优分组方案后的最少付款金额。

输入样例

4
3
2
3
2

输出样例

8

样例说明

样例中 4 本书的价格为 3、2、3、2，总原价为 3+2+3+2 = 10。
最优分组方案：将书籍分为一组 3 本，如 (3, 3, 2)和一组 1 本 2。

• 3 本组免费最低价 2，总免费金额为 2；
• 总花费 = 10 - 2 = 8