Problem Description

Takahashi is going camping with his friends.

Takahashi and his friends have two identical meat grills, and they can cook meat on both grills simultaneously. Once meat is placed on a grill, it cannot be removed or another piece of meat added until it is fully cooked. After the meat is cooked, it can be removed. It is not possible to place a single piece of meat across both grills. There are a total of $ N $ pieces of meat, numbered from $ 1 $ to $ N $. It takes time $ t_i $ to cook meat $ i $ on either grill. The actions of placing and removing meat from the grill do not take any time.

Takahashi is in charge of cooking the meat, and he needs to cook all $ N $ pieces. Since everyone is hungry, he wants to minimize the time it takes to cook all the meat.

Find the minimum time required to cook all the meat.

Input Format

The input is given from the standard input in the following format:

$ N $ $ t_1 $ $ t_2 $ : $ t_N $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 4)$, representing the number of pieces of meat.
• The next $ N $ lines contain the information about the meat. The $ i $-th line of these $ N $ lines contains an integer $ t_i $, which represents the time $t_i\ (1\ ≦\ t_i\ ≦\ 50)$ required to cook meat $ i $.

Output Format

Output the minimum time required to cook all the meat in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
4
6
7
10

Sample Output #1

14

Sample Input #2

3
1
2
4

Sample Output #2

4

Sample Input #3

1
29

Sample Output #3

29

Notes/Hints

Sample Explanation 1

One grill cooks meat $ 1 $ and meat $ 4 $, while the other grill cooks meat $ 2 $ and meat $ 3 $ in sequence (the figure below is for reference). 

Sample Explanation 2

While one grill is cooking meat $ 3 $, the other grill cooks all the remaining meat.

见题面 Input 部分

见题面 Output 部分