Знижки
Знижки
Відвідавши перед Новим роком великий магазин, ви обрали багато подарунків рідним та друзям. Зекономити певну кількість грошей вам можуть допомогти два типи передноворічних знижок, що діють у магазині:
1. При купівлі трьох товарів ви платите за них як за два найдорожчих з них.
2. При купівлі чотирьох товарів ви платите за них як за три найдорожчих з них.
Таким чином, певні товари можна обrsquo;єднати у трійки або четвірки і заплатити за них менше. Треба визначити найменшу можливу суму грошей, яка буде витрачена на придбання усіх подарунків. Наприклад, якщо ціни п'яти обраних подарунків складають: 50, 80, 50, 100, 20, то можна окремо придбати чотири перших товари, отримати за них знижку, та потім купити подарунок, що залишився за його номінальну ціну. Загалом вся покупка буде коштувати 250 грошових одиниць, замість 300.
Напишіть програму, що за цінами усіх подарунків, знаходить мінімальну суму грошей, якої вистачить на їх купівлю.
Вхідні дані
Перший рядок містить одне ціле число N0 ≤ N ≤ 10 000). Другий рядок містить Nнатуральних чисел - ціни подарунків. Сума цін усіх подарунків менша за 10^9. Об'єднувати можна не лише ті товари, що йдуть підряд у вхідних даних.
Вихідні дані Вивести одне ціле число - знайдену мінімальну суму грошей, за яку можна купити усі подарунки.
Приклад
5 50 80 50 100 20
250