Яблов и Тостов играют в игру. Изначально Яблов дает Тостову набор из n чисел, затем ребята начинают действовать следующим образом:
- Каждый раз, когда Тостов получает набор из чисел, он суммирует все числа набора и добавляет эту сумму к текущему счету. Затем он передает набор Яблову.
- Каждый раз, когда Яблов получает набор чисел, состоящий из единственного числа, он выбрасывает этот набор. Каждый раз, когда Яблов получает набор чисел, состоящий из более, чем одного числа, он разбивает этот набор на два непустых набора (делать это он может любым способом), а затем отдает оба получившихся набора Тостову.
В тот момент, когда наборов в игре не осталось, друзья смотрят на счет. Какой максимальный счет они могут получить?
Выходные данные
Выведите единственное целое число — максимальный возможный счет.
Примечание
Рассмотрим следующую последовательность действий для первого тестового примера. Изначально у Тостова набор [3, 1, 5], он добавляет к счету 9 и передает набор Яблову. Яблов разбивает набор [3, 1, 5] на два [3, 5] и [1], каждый из них передает Тостову. Получив набор [1], Тостов добавляет к счету 1 и отдает его Яблову (Яблов в свою очередь выкинет его). Получив набор [3, 5] Тостов добавляет к счету 8 и отдает его Яблову. Яблов делит набор [3, 5] единственно возможным способом: [5] и [3]. Затем он отдает оба набора Тостову. Получив набор [5], Тостов добавляет к сумме 5 и отдает набор Яблову (тот его выкидывает). Получив набор [3], Тостов добавляет к сумме 3 и отдает набор Яблову (тот его выкидывает). Итого, Тостов добавит 9 + 1 + 8 + 5 + 3 = 26. Это оптимальная последовательность действий.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 1 5
|
26
|
|
2
|
1
10
|
10
|