4480. 分饼干

【题目背景】

弗兰茜得到了一盒饼干！饼干非常美味，但是她不能独吞，因为她还有一个弟弟尼利，她要设计一种公平的分饼干的方式，但是这难住了她，于是只好请你帮忙。

【题目描述】

给定 $n$ 块饼干，每个饼干有一个质量 $a_i$，你要从这 $n$ 块饼干选择若干块，并将你所选的饼干分成两个集合 $A$ 和 $B$ ，使得 $\sum_{i\in A}a_i=\sum_{j\in B}a_j$，而剩下的饼干就留给母亲凯蒂了。

但是弗兰茜希望能吃到更多的饼干，所以，如果有多种方案，选择能使 $A$ 和 $B$ 中饼干质量和最大的方案，并输出这个质量。

【输入格式】

第一行一个整数 $n$，表示饼干数量。

接下来一行 $n$ 个数，第 $i$ 个数为表示第 $i$ 块饼干的质量 $a_i$。

【输出格式】

一行一个整数表示弗兰茜能吃到的饼干最大质量。如果弗兰茜一块饼干也吃不到，则输出 0。

【样例输入】

3
2 3 5

【样例输出】

5

【数据规模与约定】

对于 40% 的数据，$1\le n \le 16$。

对于 100% 的数据，$1\le n\le 50,1\le a_i\le 5 \times 10^5,\sum_{i=1}^n a_i \le 5 \times 10^5$。

大样例

洛谷P1651。