문제
정보올림피아드 전국대회 진출자를 N개의 팀으로 나누어 알고리즘 특강을 하려고 한다. 강사는 우리들의 능력자 근우조교와 범수 조교이다. 두 조교는 각자가 맡은 부분을 모든 팀에게 강의할 예정이다.
당연한 이야기지만 두 조교가 한 팀에게 동시에 강의 할 수 없으며 한 조교가 여러 팀을 한꺼번에 강의하지 않는다. 여러분에게 팀의 수와 각 팀이 알고리즘을 이해하고 구현하는데 걸리는 시간이 주어진다. 이때 근우 조교와 범수 조교가 강의를 모두 마치는데 걸리는 시간의 최소값은 얼마일까?
근우 조교와 범수 조교는 가능한 강의를 빨리 마치고 함께 ACM ICPC 대회 준비를 해야 한다고 한다.
각 팀의 학생들은 전국대회 진출자인 만큼 쉬지 않고 공부할 수 있으며, 우리의 조교들 또한 능력자인 만큼 쉬지 않고 강의 할 수 있을 뿐 아니라 강의실을 이동하는데 추가 시간이 들이 않는다고 한다. ^^
아래 첫 번째 입력 예를 보면 3개의 팀이 있고 각 팀은 알고리즘을 이해하고 구현하는데 2시간씩 걸린다.
한 가지 가능한 방법은 근우 조교가 1팀, 2팀, 3팀 순서로 강의 할 때, 범수조교는 같은 시간에 3팀, 1팀 2팀 순으로 강의하면 6시간이면 모든 강의가 끝난다.
두 번째 입력 예의 경우에는 근우 조교가 2팀, 3팀 순으로 강의 한 후 1시간 쉬고 1팀에게 강의 할 때, 범수조교는 1팀, 2팀, 3팀 순으로 강의한 후 1시간 쉬면서 근우 조교가 강의를 마치는 것을 기다린다.
따라서 두 조교가 모든 강의를 마치는데 걸리는 시간은 8시간이다.
입력
첫 행에 팀 수 N( 1 ≤ N ≤ 300,000) 입력된다.
두 번째 행에 각 팀이 알고리즘을 이해하고 구현하는데 걸리는 시간 Ti ( 1≤ Ti ≤ 300,000)이 공백으로 구분하여 주어진다.
입력 데이터의 40%는 N ≤ 7 이다.
출력
두 조교가 모든 강의를 끝내는데 걸리는 최소시간을 출력한다.
예제1
입력
3
222
출력
6
예제2
입력
3
412
출력
8
예제3
입력
4
1321
출력
7
출처
COCI 2014/2015 contest4 3