도서관

방학 동안 바이트타자르는 좋은 문학의 애호가가 되어 도서관에서 빌린 책을 아주 많이 읽었다. 어느 날 친구 뷔욘테크가 찾아와 빌린 책 가운데 한 권에 관심을 보였고, 거듭된 부탁 끝에 바이트타자르는 그 책을 빌려주기로 했다.

방학은 금세 지나가고 새 학년이 시작되었다. 책을 반납할 때가 되자 바이트타자르는 그 책을 뷔욘테크에게 빌려주었다는 것을 떠올렸는데, 뷔욘테크는 그만 책을 잃어버렸다고 털어놓았다. 이야기를 들은 사서들은 그 대가로 바이트타자르에게 도서관 카드 정리를 돕게 하기로 했다.

카드들은 크기가 제각각인, 이미 정렬된 여러 개의 파일에 나뉘어 있다. 바이트타자르가 할 일은 이 파일들을 하나의 정렬된 파일로 합치는 것이다. 그는 한 번에 두 개의 파일만 합칠 수 있으며, 단순화를 위해 두 파일을 합치는 데 걸리는 시간은 두 파일 길이의 합과 같다고 하자.

파일의 개수와 각 파일의 길이가 주어질 때, 모든 파일을 하나로 합치는 데 필요한 최소 총 시간을 구하는 프로그램을 작성하여라.

첫째 줄에 합쳐야 할 파일의 개수 $n$ ($2 \le n \le 100000$)이 주어진다. 둘째 줄에는 $n$개의 정수 $s_1, s_2, \dots, s_n$이 공백 하나로 구분되어 주어지며, $s_i$는 $i$번 파일의 길이이다 ($1 \le s_i \le 10000$).

모든 파일을 하나로 합치는 데 필요한 최소 총 시간을 정수 하나로 한 줄에 출력한다.