На столе лежит n верёвок разной длины. Вам нужно связать их все в одну длинную верёвку. За одну операцию можно взять любые две верёвки и связать их в одну — стоимость такой операции равна сумме длин этих двух верёвок.
Например, если связать верёвки длиной 3 и 5, получится одна верёвка длиной 8, а стоимость операции — 8. Эту новую верёвку можно затем связывать с другими.
Требуется найти минимальную суммарную стоимость, за которую можно связать все n верёвок в одну.
Формат входных данных
В первой строке записано натуральное число n (1 ≤ n ≤ 50 000) — количество верёвок.
Во второй строке через пробел записаны n натуральных чисел a1, a2, …, an (1 ≤ ai ≤ 10 000) — длины верёвок.
Формат выходных данных
Выведите одно целое число — минимальную суммарную стоимость связывания всех верёвок в одну. Если верёвка одна (n = 1), выведите 0.
Внимание: ответ может не помещаться в 32-битный целочисленный тип. В языке C++ используйте тип long long; в Python ограничений нет.
Пояснение к первому примеру
Оптимальная последовательность: связываем 2 и 3 (стоимость 5), получаем набор {4, 5, 6}. Связываем 4 и 5 (стоимость 9), получаем {6, 9}. Связываем 6 и 9 (стоимость 15). Итого: 5 + 9 + 15 = 29.
| № | Входные данные | Выходные данные |
|
1
|
4
4 3 2 6
|
29
|
|
2
|
1
5
|
0
|
|
3
|
5
2 2 2 2 2
|
24
|