Задача Discount. Відвідавши перед Різдвом великий магазин, ви обрали багато подарунків рiдним та друзям. Зекономити певну кількість грошей вам можуть допомогти два типи знижок, що дають у магазина:
1. при купівлі 3-х товарів, Ви платите за них як за 2 найдорожчих з них;
2. при купівлі 5-и товарів, Ви платите за них як за 3 найдорожчих з них.
Таким чином, певнi товари можна об’єднати у трійки або п’ятірки i заплатити за них менше. Треба визначити найменшу можливу суму грошей, яка буде витрачена на придбання усіх подарунків.
Напишуть програму, що за цінами усіх подарунків, знаходить мінімальну суму грошей, якої вистачить на їх купівлю.
Технічні умови. Програма Discount читає з пристрою стандартного введення ціле число N (1⩽ N⩽123456). Другий рядок містить N натуральних чисел — ціни подарунків. Сума цін усіх подарунків менша за 1018. Об’єднувати можна не лише ті товари, що йдуть підряд у вхідних даних.
Програма виводить на пристрій стандартного виведення єдине число — знайдену мінімальну суму грошей, за яку можна купити усі подарунки.
Приклад
|
Введення |
Виведення |
|
5 50 80 50 100 20 |