Kile 和 Pogi 在街上捡到了 $N$ 张纸币。在确认找不到原失主后，他们决定瓜分这些纸币。最终，他们希望两人能“分到”相同数量的钱，因此他们决定以这种方式来分配纸币。当然，最后谁也没分到的纸币总额应该尽可能少。

由于他们不能把剩下的纸币直接扔在街上，他们决定去附近的一家赌场，把所有的剩余纸币都押在“红色”上，希望能赢得两倍的赌注。轮盘最终停在了（这次对他们来说很幸运的）数字 13 上，我们的两位主角决定平分赢来的钱。赌场的赔付方式使得 Kile 和 Pogi 总是能够将赢来的钱平分为两等份。

由于肾上腺素激增，这两个男孩失去了他们的数学计算能力。请帮助他们计算出每个人最终能带回家多少钱。

输入格式

输入的第一行包含一个整数 $N$（$1 \le N \le 500$），表示街上纸币的数量。

接下来的 $N$ 行，每行包含一个正整数 $c_i$，表示第 $i$ 张纸币的面值，单位为库纳（kn）。纸币的总面值不会超过 $100\,000$ kn。

输出格式

输出每个人最终带回家的金额。

子任务

• 在价值 50 分的测试数据中，$N \le 13$。
• 在价值 70 分的测试数据中，$N \le 50$，且纸币总面值最多为 $1000$ kn。

样例

输入样例 1

4
2
3
1
6

输出样例 1

6

输入样例 2

5
2
3
5
8
13

输出样例 2

18

说明

样例 1 说明

Kile 拿了面值为 2、3 和 1 kn 的纸币，Pogi 拿了面值为 6 kn 的纸币。

样例 2 说明

Kile 拿了面值为 5 和 8 kn 的纸币，Pogi 拿了面值为 13 kn 的纸币。剩下的纸币面值为 2 和 3 kn，男孩们在赌场中将它们“翻倍”。每个人最终获得的金额为 $13 + 5 = 18$ kn。