10967. Комерційний калькулятор
Фірма OISAC випустила нову версію калькулятора. Цей калькулятор бере з користувача гроші за арифметичні операції. Вартість кожної операції у доларах дорівнює 5% від числа, що є результатом операції.
На цьому калькуляторі потрібно обчислити суму \(N\) натуральних чисел (відомі числа). Неважко помітити, що від того, в якому порядку ми складатимемо ці числа, іноді залежить, в яку суму грошей нам обійдеться обчислення суми чисел (тим самим виявляється порушений класичний принцип "від перестановки місць доданків сума не змінюється").
Наприклад, нехай нам потрібно скласти числа 10, 11, 12 і 13. Тоді, якщо ми спочатку складемо 10 і 11 (це обійдеться нам в 1.05 €), потім результат з 12 (1.65 €), а потім з 13 (2.3 €), то всього ми заплатимо 5 €, якщо спочатку окремо скласти 10 і 11 (1.05 €), потім 12 і 13 (1.25 €) і, нарешті, скласти між собою два отримані числа (2.3 €), то в результаті ми заплатимо лише 4.6 €.
Напишіть програму, яка визначатиме, за яку мінімальну суму можна знайти суму даних \(N\) чисел.
Формат вхідних даних
Перший рядок вхідних даних містить число \(N\) (\(2 ≤ N ≤ 10^5\)).
У другому рядку задано \(N\) натуральних чисел, кожне з яких не перевищує 10000.
Формат вихідних даних
Визначте, скільки грошей нам знадобиться знаходження суми цих \(N\) чисел. Результат має бути виведений із двома знаками після десяткової точки.
Приклад вхідних даних
4
10 11 12 13
Приклад вихідних даних
4.60
Приклад вхідних даних
2
1 1
Приклад вихідних даних
0.10
Коментарі