C + + dynamic programming or C language recursion can be used

The phenomenon and background of the problem ： Construction of gate posts

You decide to stack some stones of different heights into the columns on the left and right sides of the gate , And hope the height of the gate is the highest . The columns on the left and right sides must be of equal height , Otherwise, the gate cannot be installed with beams .

for example , If the height of the three stones is 1、2 and 3, Then they can be stacked to a height of 6 Stone pillars . If there are two other pieces, the height is 2 and 4 The stone of , Then you can form the columns on both sides of the gate , The height of the gate is 6.

Return to the maximum possible height of the gate . If this pile of stones can't install the gate , Please return 0.

There may be several stones of the same height .

Output ：

Input format ：
The first line is an integer n, It means how many stones there are . The second behavior is the height of each stone , Space off .
Output format ：
An integer , Indicates the maximum possible height of the gate .

Enter the data range ：
0<=n<=20
1<= The height of each stone <=1000
The total height of the stone <=5000

Example 1：
Input ：
4
1 2 3 6
Output ：
6
Tips ： The columns on both sides are made of stones 1+2+3 and 6 form .

Example 2：
Input ：
6
1 2 3 4 5 6
Output ：
10
Tips ： The columns on both sides are made of stones 2+3+5 and 4+6 form .

Example 3：
Input ：
2
1 2
Output ：
0
Tips ： Cannot form a column with equal height on both sides .

Example 4：
Input ：
20
1 2 4 8 16 32 64 128 256 512 50 50 50 150 150 150 100 100 100 123
Output ：
Please provide according to the program running results