EduBrick

L. Наименьшая стоимость склейки

2000 мс · 256 МБ · всё или ничего

Есть nn куч камней. За один ход можно склеить любые две кучи; стоимость хода равна суммарному размеру склеиваемых куч. Склейте всё в одну кучу с наименьшей суммарной стоимостью.

Формат ввода

В первой строке - число nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5).

Во второй - nn размеров куч, целых от 1 до 10910^9.

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

Одно число - наименьшая суммарная стоимость склейки.

Примеры

ввод
4
1 2 3 4
вывод
19
ввод
1
5
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.