时间限制：1秒　　内存限制：256M

---

【题目描述】

　　由于期末考试成绩优异，小H和小Z两人得到老师奖励的 N 张钞票。然后他们分别取走若干张钞票，使得每人所得的总金额相同。同时要尽可能保证分得的总金额最大。
接着，他们会带着剩下的钞票到老师那里，再次从老师那里得到等于剩余数量金额的奖励。然后，他们会将把这些钞票再次平分，并加入每个人的总金额中。
那么每个人能够分得的总金额是多少？

【输入格式】

　　第一行，一个整数N。
接下来的N行，每行一个正整数ci，表示第i张钞票的面额。保证N张钞票的总金额不超过105。

【输出格式】

　　输出每个人能够分得的总金额。

【输入输出样例1】

　Input

4
2
3
1
6

　Output

6

【样例1说明】

　　小H 可以选择取走面额分别为 2,3,1 的钞票，而小Z 可以取走面额为 6 的钞票。由于没有剩余钞票，因此每人所得总金额为6。

【输入输出样例2】

　Input

5
2
3
5
8
13

　Output

18

【样例2说明】

　　小H可以选择取走面额分别为5,8的钞票，而小Z可以取走面额为13的钞票。剩下的钞票面额分别为2,3，因此在会得到老师补充金额5，所以每人所得总金额为 13+5=18。

【数据限制】

　　对于 50% 的数据，N≤13。
对于 70% 的数据，N≤50，∑ci≤1000。
对于 100% 的数据，1≤N≤500，∑ci≤100000。

【来源】

　　Mr.he