10059 허프만 코딩 Gold IV

문제

N개의 파일을 하나로 합치려고 한다. 두 파일을 합칠 때 드는 비용은 두 파일 크기의 합이다. 모든 파일을 하나로 합칠 때 드는 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 파일의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에 N개의 파일 크기가 공백으로 구분되어 주어진다. 각 크기는 1 이상 10,000 이하이다.

출력

최소 비용을 출력한다.

4
1 2 3 4

19