Se citesc n sfori, de lungimi date. Costul de a lipi doua sfori intr-una singura este egal cu suma lungimilor lor. Determinati, folosind metoda Greedy, costul total minim necesar pentru a uni toate cele n sfori intr-una singura.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n lungimi.
- Date de iesire
- Se afiseaza un singur numar: costul total minim.
- Restrictii
- 1 <= n <= 100000, 1 <= lungime <= 10^9
Exemple
Exemplul 1
Intrare
4 4 3 2 6
Iesire
29
Exemplul 2
Intrare
3 1 8 3
Iesire
16