Meterul Piperel are N tevi, cu lungimile date, pe care trebuie sa le imbine intr-o singura teava. De fiecare data poate imbina doar doua tevi, iar teava noua se aseaza langa celelalte. Imbinarea a doua tevi cu lungimile x si y are costul x+y si produce o teava de lungime x+y. Calculati costul minim necesar pentru a imbina toate cele N tevi intr-una singura.
- Date de intrare
- Pe prima linie se citeste N. Pe a doua linie se citesc N numere, lungimile tevilor.
- Date de iesire
- Se afiseaza un singur numar intreg: costul minim total.
- Restrictii
- 1 <= N <= 2000, 1 <= lungime <= 10^6
Exemple
Exemplul 1
Intrare
10 7 5 3 2 3 10 7 4 9 6
Iesire
180
Exemplul 2
Intrare
2 5 8
Iesire
13