Ligar os cabos
Imagine que tem n cabos, cada um com um determinado comprimento, e pretende uni-los todos num único cabo. Para ligar dois cabos com comprimentos x e y, tem de pagar x + y. Depois de os ligar, o novo cabo resultante terá comprimento x + y.
Qual é o valor mínimo que terá de gastar para ligar todos os cabos?
Entrada
A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ ), que representa o número de cabos.
A linha seguinte contém inteiros separados por espaço (1 ≤ ≤ ), que são os comprimentos dos cabos.
Saída
O programa deve imprimir o valor mínimo que se gasta para ligar todos os cabos.
Exemplos
Entrada | Saída |
|---|---|
5 1 2 3 6 2 | 30 |
Explicação
Ligar 1 e 2 ⇒ pagar 3 ⇒ 3 3 6 2
Ligar 2 e 3 ⇒ pagar 5 ⇒ 5 3 6
Ligar 3 e 5 ⇒ pagar 8 ⇒ 6 8
Ligar 6 e 8 ⇒ pagar 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB