Задачи / Статистика /

Номер задачи - 13

Задача Коммерческий калькулятор

Ограничение: 3 сек. на тест

Фирма 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<=100000). Во второй – через пробел N натуральных чисел, которые нужно сложить, каждое из них не превышает 10000.

Формат выходных данных

Одно вещественное число, сколько денег нам потребуется на нахождение суммы этих N чисел. Результат должен быть выведен с двумя знаками после десятичной точки.

Примеры