问题描述

Kile 和 Pogi 在街上捡到了 $N$ 张钞票，第 $i$ 张钞票面值为 $c_i$（$1 \le i \le N$）．它们等了半天也没有人来认领，于是他们打算平分这些钱．他们的计划是，每人先拿走一些钞票，需要满足每人拿到的钞票的总金额相同，并且每人分到的钱越多越好。如果还有剩的钱，就拿去买刮刮乐。这是因为如果刮刮乐中奖了就会获得双倍的奖励，他们就能平分这笔钱。

如果他们中奖了，每人将分到多少钱？

数据范围

• $1 \le N \le 500$
• 钞票的面值是正整数，且总额不超过 $100000$。

本题有 20 个测试点。测试点 1 到 10 满足 $N \le 13$。测试点 11 到 14 满足 $N \le 50$ 且总钱数不超过 1000 元。

输入

第一行一个正整数 $N$。接下来 $N$ 行，每行一个正整数 $c_i$。

输出

一个整数，表示每人分到多少钱。

样例输入 1

4
2
3
1
6

样例输出 1

6

Kile 拿走第 1，2，3 张钞票。Pogi 拿走第 4 张钞票。

样例输入 2

5
2
3
5
8
13

样例输出 2

18

Kile 拿走第 3、4 张钞票，Pogi 拿走第 5 张钞票，每人得到 13 元。剩下 5 元钱。如果中奖了，每人还能再得 5 元，一共 18 元。