题目描述

书店搞活动了！

现在，您可以一次性购买 $3$ 本书，而三本书中，您只需要付较贵的两本书的钱。

注意，这种优惠在一次性购买 $1$ 或 $2$ 本书时，不存在。

现在，您希望花最少的钱买下 $n$ 本书。

请求出买下 $n$ 本书需花的最少钱数。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，一行一个整数 $c_i$，第 $i$ 行表示第 $i$ 本书的价格。

输出格式

仅一行一个整数，表示买下 $n$ 本书需花的最少钱数。

4
3
2
3
2 

8

6
6
4
5
5
5
5

21

提示

【样例解释】

样例 1 解释

一起买价格为 $3,2,2$ 的三本书，剩下的一本书单独买即可。

样例 2 解释

一起买价格为 $6,4,5$ 的三本书，而后一起买价格为 $5,5,5$ 的三本书。

【数据范围及限制】

• 对于 $50\%$ 的数据，保证 $n\le 2\times 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$1\le c_i\le 10^5$。

【说明】

本题满分 $80$ 分。

本题译自 Croatian Open Competition in Informatics 2015/2016 Contest #1 T2 AKCIJA。