Preparation Lectures

Time limit2sMemory limit32 MB

Summary

Both lecturers teach each of N teams for t_i time and the goal is the shortest overlap-free schedule for all lectures.

Level: Medium7 of 10
Topics: Greedy, Sorting, Math
Solved: No attempts yet

Problem

Ante and Goran are coaching $N$ teams of students for a programming competition. Each of the two has one algorithm to explain, so every team has to attend one lecture by Ante and one lecture by Goran.

Team $i$ needs $t_i$ units of time to understand and implement an algorithm, and that time is the same for both lectures. A lecture runs without interruption. Ante and Goran cannot lecture the same team at the same moment, and neither of them can lecture two teams at the same moment. Either lecturer is allowed to stay idle at any moment, and a team may attend the two lectures in either order.

Find the smallest amount of time in which both lecturers finish all of their lectures.

Input

The first line contains the integer $N$ , the number of teams.

The second line contains $N$ integers $t_1, t_2, \dots, t_N$ separated by spaces, where $t_i$ is the time team $i$ needs to understand and implement an algorithm.

Every number in the input lies in the interval $[1, 3 \times 10^5]$ .

Output

Print the smallest amount of time as a single integer.

Note

In the first example every team spends 2 units of time. Ante can lecture team 1, then team 2, then team 3, while Goran lectures team 3, then team 1, then team 2.

In the second example Ante can lecture team 2 and team 3 in that order, stay idle for 1 unit of time, and then lecture team 1, while Goran lectures team 1, then team 3, then team 2.

Examples3

Example 1
Input
```
3
2 2 2
```
Expected output
```
6
```
Example 2
Input
```
3
4 1 2
```
Expected output
```
8
```
Example 3
Input
```
4
1 3 2 1
```
Expected output
```
7
```