说明

小y的班级里共有 $n$ 位同学,现有一个数学竞赛的活动，将班里的 $n$ 位学生平均分成两队互相竞争。

现在小y获知 $n$ 位同学的数学成绩，要求他从全班同学中选出一半数量的同学，并要求这些同学成绩之和不超过(所有人分数和一半)的情况下，尽可能高。

这样分成的两队实力是最平均的，你来帮助小y完成这个程序吧。

输入格式

第一行有一个整数，表示班级的学生人数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $a_i$ 表示第 $i$ 位同学的成绩。

对于30%的测试点，保证 $1 \leq n \leq 20$，$1 \leq a_i \leq 100$，数据保证 $n$ 均为偶数

对于全部的测试点，保证 $1 \leq n \leq 100$，$1 \leq a_i \leq 100$，数据保证 $n$ 均为偶数。

样例解释在最下方

输出格式

输出一行一个整数表示答案

样例

8
77
56
46
77
56
77
84
77

273

提示

样例解释: 班级总分为 $550$，总分的一半是 $275$，选则成绩分别为 $56,77,84,56$ 的同学可以达到总分 $273$，四位同学是不超过 $275$ 的最大值。