eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Знижки

Знижки

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Відвідавши перед Новим роком великий магазин, ви обрали багато подарунків рідним та друзям. Зекономити певну кількість грошей вам можуть допомогти два типи передноворічних знижок, що діють у магазині:

1. При купівлі трьох товарів ви платите за них як за два найдорожчих з них.

2. При купівлі чотирьох товарів ви платите за них як за три найдорожчих з них.

Таким чином, певні товари можна обrsquo;єднати у трійки або четвірки і заплатити за них менше. Треба визначити найменшу можливу суму грошей, яка буде витрачена на придбання усіх подарунків. Наприклад, якщо ціни п'яти обраних подарунків складають: 50, 80, 50, 100, 20, то можна окремо придбати чотири перших товари, отримати за них знижку, та потім купити подарунок, що залишився за його номінальну ціну. Загалом вся покупка буде коштувати 250 грошових одиниць, замість 300.

Напишіть програму, що за цінами усіх подарунків, знаходить мінімальну суму грошей, якої вистачить на їх купівлю.

Вхідні дані

Перший рядок містить одне ціле число N0N10 000). Другий рядок містить Nнатуральних чисел - ціни подарунків. Сума цін усіх подарунків менша за 10^9. Об'єднувати можна не лише ті товари, що йдуть підряд у вхідних даних.

Вихідні дані Вивести одне ціле число - знайдену мінімальну суму грошей, за яку можна купити усі подарунки.

Приклад

Вхідні дані #1
5
50 80 50 100 20
Вихідні дані #1
250
Автор Шаміль Ягіяєв
Джерело 2008 XXI Всеукраїнська олімпіада з інформатики, Львів, Квітень 5 - 11, тур 2