Conecta los cables
Dado
n cables con sus longitudes, deseas unir todos esos cables para formar un solo cable de mayor longitud. Para conectar dos cables de longitudes x y y, debes pagar x + y. Después de conectarlos, el cable resultante tiene una longitud de x + y.¿Cuál es la cantidad mínima que podrías gastar para unir todos los cables?
Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ ), la cantidad de cables.La siguiente línea contiene enteros separados por espacio (1 ≤ ≤ ), que representan las longitudes de los cables.
Salida
El programa debe imprimir la cantidad mínima que se gastará al unir todos los cables.
Ejemplos
Entrada | Salida |
5
1 2 3 6 2 | 30 |
Explicación
- Conectar 1 y 2 ⇒ pagar 3 ⇒ 3 3 6 2
- Conectar 2 y 3 ⇒ pagar 5 ⇒ 5 3 6
- Conectar 3 y 5 ⇒ pagar 8 ⇒ 6 8
- Conectar 6 y 8 ⇒ pagar 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB