Joining Wires

Medium#greedy #heap· solved by 0 · time limit 2.0 s

You have $n$ wires of given lengths. Joining two wires of lengths $x$ and $y$ costs $x + y$ and gives one wire of length $x + y$ . Join them all into one wire at minimum total cost.

Always join the two shortest — a min-heap makes that fast.

Input

$n$ , then $n$ lengths.

Output

The minimum total cost.

Constraints

$1 \le n \le 10^5$ , $1 \le$ length $\le 10^4$ — use 64-bit totals.

Sample 1

Input

4
4 3 2 6

Output

Sample 2

Input

1
5

Output