Statement

As his friends keep self inviting at his place, Luca is constantly looking for ways to save money when buying food. Supermarkets are an excellent spot for this, with their never-ending promotional offers. In particular, "buy 3, pay for 2" is especially appealing when you need to buy a lot of things and you are certain that you will not waste a significant fraction of the goods. The details of the promotions are rather simple: each person can use this offer only once, bringing three items to the cashier and skipping the payment of the less expensive one. If one buys less than three items, no particular discount applies. Luca and his friends made a list of N goods they want to buy, along with their prices P_i. They are now heading towards the exit and they want to distribute the items among them so that the overall expense (that is, the sum of the amount each of them pays) is the least possible. How much will they pay?