A. Яблов и Тостов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Яблов и Тостов играют в игру. Изначально Яблов дает Тостову набор из n чисел, затем ребята начинают действовать следующим образом:

  • Каждый раз, когда Тостов получает набор из чисел, он суммирует все числа набора и добавляет эту сумму к текущему счету. Затем он передает набор Яблову.
  • Каждый раз, когда Яблов получает набор чисел, состоящий из единственного числа, он выбрасывает этот набор. Каждый раз, когда Яблов получает набор чисел, состоящий из более, чем одного числа, он разбивает этот набор на два непустых набора (делать это он может любым способом), а затем отдает оба получившихся набора Тостову.

В тот момент, когда наборов в игре не осталось, друзья смотрят на счет. Какой максимальный счет они могут получить?

Входные данные

В первой строке записано единственное целое число n (1 ≤ n ≤ 3·105). Во второй строке записано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106) — набор, который Яблов дал Тостову изначально.

Выходные данные

Выведите единственное целое число — максимальный возможный счет.

Примеры
Входные данные
3
3 1 5
Выходные данные
26
Входные данные
1
10
Выходные данные
10
Примечание

Рассмотрим следующую последовательность действий для первого тестового примера. Изначально у Тостова набор [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. Это оптимальная последовательность действий.