카드 묶음 정렬하기

정렬된 숫자 카드 묶음 여러 개가 있다. 카드가 각각 A장과 B장인 두 묶음을 하나로 합치려면 A+B번의 비교가 필요하다.

책상 위에 있는 모든 카드 묶음을 하나의 묶음으로 합치려고 한다. 어떤 두 묶음을 먼저 고르느냐에 따라 전체 비교 횟수가 달라진다. 예를 들어 10장, 20장, 40장짜리 묶음이 있을 때 10장과 20장을 먼저 합치면 이후 30장과 40장을 합쳐 총 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 반대로 10장과 40장을 먼저 합치면 총 (10 + 40) + (50 + 20) = 120번이 필요하므로 더 비효율적이다.

N개의 숫자 카드 묶음 크기가 주어질 때, 모든 묶음을 하나로 합치는 데 필요한 최소 비교 횟수를 구하시오.

첫째 줄에 카드 묶음의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개의 줄에는 각 카드 묶음의 크기가 한 줄에 하나씩 주어진다. 각 묶음의 크기는 1 이상 1,000 이하인 정수이다.

모든 카드 묶음을 하나로 합치는 데 필요한 최소 비교 횟수를 첫째 줄에 출력한다.