R대학교의 루루 교수는 학생들의 레포트를 채점할 때 나름의 검토 방식을 가지고 채점한다.

우선, 루루는 학생들이 제출한 레포트 중 2개를 선택해 레포트의 한 페이지씩 모두 검토한 다음, 하나의 레포트로 합친다.
그리고 다시 남아있는 레포트와 합친 레포트 중 2개를 선택해 한 페이지 검토하고, 검토가 완료되면 하나의 레포트로 합친다.
만약 모든 레포트가 하나의 레포트로 합쳐지면 검토를 마무리한다.

루루는 집중력을 최대한 유지하기 위해 최소한의 페이지를 검토하려고 한다.
제출한 레포트와 각각의 레포트가 가진 페이지 수가 주어질 때, 루루가 검토할 전체 페이지 수의 최솟값을 구하시오.

첫째 줄에는 루루가 검토할 레포트의 개수(N)가 주어진다. ( 1<=N<=100,000 )
둘째 줄에는 각각의 레포트가 가진 페이지 수(P_i)가 공백으로 구분되어 주어진다. ( 1<=P_i<=100,000 )

루루가 검토할 전체 페이지 수의 최솟값을 출력한다.

만약 3개의 레포트의 페이지 수가 [10p, 5p, 17p]이라면 10p와 5p 레포트를 선택해 총 15p를 검토하고 하나의 보고서로 합친다.
그리고 합친 15p 보고서와 남아있는 17p 보고서를 선택해 총 32p를 검토하고 하나의 보고서로 합치고 검토를 마무리한다.
이 경우, 루루가 검토한 총 페이지 수는 (15p + 32p) = 47p가 되며, 루루가 검토하는 전체 페이지 수의 최솟값이다.

 CSL2023