P6530 [COCI 2015/2016 #1] AKCIJA

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.

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 a single integer, representing the minimum total cost to buy $n$ books.

#### 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](https://hsin.hr/coci/archive/2015_2016) [Contest #1](https://hsin.hr/coci/archive/2015_2016/contest1_tasks.pdf) T2 AKCIJA. Translated by ChatGPT 5