В этой задаче вы будете перекладывать камни. Изначально есть n кучек камней. Кучка i весит aiкилограммов. Кучки можно объединять. При объединении кучек i и j затрачивается ai + aj единиц энергии, при этом две исходные кучки пропадают и появляется кучка весом ai + aj.
Определите наименьшее количество энергии, которое надо затратить для объединения всех кучек в одну.
В первой строке дано число n (1 ≤ n ≤ 105)
В следующей строке записаны массы кучек через пробел — ai (1 ≤ ai ≤ 106)
Выведите единственное число — минимальную энергию, которую надо затратить на объединение всех кучек.
|
2 2 6 |
8 |
|
3 6 2 4 |
18 |