프로그램 명: coci_pripreme
제한시간: 2 초

[문제 요약]

2개의 강의실이 있다.

각 팀은 2개 각각의 강의실에서 강의를 하나씩 들어야한다.

N개의 팀이 한개의 강의를 듣는데 걸리는 시간은 T[n]이고, 한 강의실을 두개 이상의 팀이 동시에 사용할 수 없을때, 모든 팀이 강의듣기를 완료하는 최소 시간을 구하여라.

입력

출력

모든 팀이 강의듣기를 완료하는 최소 시간만을 출력한다.

입출력 보충설명 

입출력예제 1 : 
0~2 : 팀 1과 팀 2가 각각 1,2 강의실에서 강의를 듣는다. 
팀\강의실    1      2 
1           들음   안들음 
2         안들음   들음 
3         안들음   안들음 

2~4 : 팀 3과 팀 1이 각각 1,2 강의실에서 강의를 듣는다. 
팀\강의실    1      2 
1           들음   들음 
2         안들음   들음 
3           들음   안들음 

4~6 : 팀 2와 팀 3이 각각 1,2 강의실에서 강의를 듣는다. 
팀\강의실    1      2 
1           들음   들음 
2           들음   들음 
3           들음   들음 

최소시간 : 6
Ante and Goran are preparing N teams of young ambitious students for a student programming competition of students from University of Zagreb. Both of them have one algorithm they have to explain to each team. Of course, both can’t work with the same team at the same time and none of them can work with multiple teams simultaneously.

You are given the time it takes for each team to understand and implement an algorithm. Each algorithm lecture has to be done without interruption. Determine the minimal time required for Ante and Goran to do their lectures!

For additional explanation, consult the sample tests clarifications.

입력

The first line of input contains the integer N, the number of teams. The following line contains N space separated integers, where the i-th integer denotes the time required for the i-th team to understand and implement an algorithm. All numbers in the input will belong to the interval [1, 3*10^5].

출력

The first and only line of output must contain the required number from the task.

입출력 예


입력

3
2 2 2

출력

6

입력

3
4 1 2

출력

8

입력

4
1 3 2 1

출력

7

Clarification of the first example: Each team needs 2 units of time to understand and implement an
algorithm. One of the possible schedules is that Ante gives his lectures to team 1, team 2 and team 3, respectively,
and Goran to team 3, team 1 and team 2, respectively.
Clarification of the second example: One of the optimal schedules is that Ante gives lectures to team 2,
team 3 and team 1, respectively, but with a pause lasting 1 unit of time between team 3 and team 1. Goran
will give lectures to team 1, team 3 and team 2, respectively.

출처:2013/2014 contest4 3/6
요약: baji072
[질/답] [제출 현황] [푼 후(1)]
[ 채 점 ] [홈으로]  [뒤 로]