문제

2 seconds, 32 MB, 100 points 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 ith integer denotes the time required for the ith team to understand and implement an algorithm. All numbers in the input will belong to the interval [1, 3 · 105].

출력

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

예제 입력 1

3
2 2 2

예제 출력 1

6

예제 입력 2

3
4 1 2

예제 출력 2

8

예제 입력 3

4
1 3 2 1

예제 출력 3

7