Description

The bookstore is running a promotion.

Now, you can buy $3$ books at once, and among the three books, you only need to pay for the two more expensive ones.

Note that this discount does not apply when buying $1$ or $2$ books at once.

Now, you want to spend as little money as possible to buy $n$ books.

Please output the minimum total cost to buy all $n$ books.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain an integer $c_i$. The $i$-th line gives the price of the $i$-th book.

Output Format

Output a single integer, representing the minimum total cost to buy $n$ books.

4
3
2
3
2 

8

6
6
4
5
5
5
5

21

Hint

Sample Explanation

Sample 1 Explanation

Buy the three books priced $3,2,2$ together, and then buy the remaining book separately.

Sample 2 Explanation

Buy the three books priced $6,4,5$ together, and then buy the three books priced $5,5,5$ together.

Constraints

• For $50\%$ of the testdata, $n\le 2\times 10^3$ is guaranteed.
• For $100\%$ of the testdata, $1\le n\le 10^5$ and $1\le c_i\le 10^5$ are guaranteed.

Notes

This problem is worth $80$ points in total.

Translated from Croatian Open Competition in Informatics 2015/2016 Contest #1 T2 AKCIJA.

Translated by ChatGPT 5