题目描述

给定 n 个自然数：a1,a2,...,an。甲乙两人分别取走其中的一部分数字，而且两人各自取走的数字之和必须一样大。请输出他们每人可以取走的数字之和的最大值。如果不能拿走任何数字，输出 0。

输入格式

第一行：单个正整数 n；
第二行：n 个自然数，表示 a1,a2,...,an。

输出格式

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

数据范围

对于 50% 的数据，1≤n≤13；

对于 100% 的数据，1≤n≤500；

0≤ai≤100000，a1+a2+...+an≤200000

样例数据

输入:

4

2 3 1 6

输出:

6

输入:

5

2 3 5 8 13

输出:

13