题目描述

给定 $n$ 个整数：$a_1,a_2,\cdots,a_n$。小爱和小艾可以取走其中的一部分数字，而且她们各自取走的数字之和必须一样大。

请输出小爱能够取走的数字之和的最大值。如果不能拿走任何数字，输出 $0$。

输入格式

第一行：单个整数 $n$； 第二行：$n$ 个整数，表示 $a_1,a_2,\cdots,a_n$。

输出格式

单个整数：表示小爱拿走的数字之和的最大值。

4
2 3 1 6

6

5
2 3 5 8 13

13

数据范围

• 对于 $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$