Problem5543--平分数字

5543: 平分数字

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

给定 $n$ 个自然数:$a_1,\ a_2,\ \cdots,\ a_n$。甲乙两人分别取走其中的一部分数字,而且两人各自取走的数字之和必须一样大。请输出他们每人可以取走的数字之和的最大值。如果不能拿走任何数字,输出 $0$。

Input

第一行:单个正整数 $n$;
第二行:$n$ 个自然数,表示 $a_1,\ a_2,\ \cdots,\ a_n$。

Output

单个整数:表示甲乙能拿走的数字和的最大值。

Constraints

对于 $50\%$ 的数据,$1\leq n\leq 13$;
对于 $100\%$ 的数据,$1\leq n\leq 500$;
$0\leq a_i\leq 100000,\ a_1+a_2+\cdots+a_n\leq 200000$。

Sample 1 Input

4
2 3 1 6

Sample 1 Output

6
$2+3+1=6$。

Sample 2 Input

5
2 3 5 8 13

Sample 2 Output

13
$2+3+8=13$。

Source/Category