Collega i cavi
Dato
n cavi con le rispettive lunghezze, si desidera collegarli tutti per formare un unico cavo di grande lunghezza. Per collegare due cavi di lunghezza x e y, occorre pagare x + y. Una volta uniti, il cavo risultante avrà lunghezza x + y.Qual è la cifra minima da spendere per collegare tutti i cavi?
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ ), il numero di cavi.La riga successiva contiene numeri interi separati da uno spazio, (1 ≤ ≤ ), che rappresentano le lunghezze dei cavi.
Output
Il programma deve stampare il costo minimo necessario per collegare tutti i cavi.
Esempi
Input | Output |
5
1 2 3 6 2 | 30 |
Spiegazione
- Collega 1 e 2 ⇒ paga 3 ⇒ 3 3 6 2
- Collega 2 e 3 ⇒ paga 5 ⇒ 5 3 6
- Collega 3 e 5 ⇒ paga 8 ⇒ 6 8
- Collega 6 e 8 ⇒ paga 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB