题目描述

班级要组织一场综合能力竞赛，班里共有 $n$ 位学生，将分成两队互相竞争。

老师找到了越越并给了越越一张全班同学综合能力测试的成绩，要求他从全班同学中选出一半，并要求这些同学综合能力测试的成绩之和在不超过班级总分一半的前提下尽量达到最高。这样分成的两队实力是最平均的。越越堆着满脸的笑容找到了你，你就帮他写一个程序吧。

输入格式

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

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

输出格式

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

8
77
77
56
77
84
77
56
46

273

提示

样例 1 解释

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

数据规模与约定

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