作业已超过截止时间，您无法递交本题目。

题目背景

DALEK 们又要出动了，对付难缠的时间领主。其中一部分被组织成先遣队，抗击时间领主；一部分则留在老窝，防止时间领主在老巢里发动袭击。现在戴沃斯开始选人了。

题目描述

戴沃斯有一张包含所有 DALEK 的基本信息的表，有着每个 DALEK 的战斗力。现在他想从所有 DALEK 中选出 一半，并要求这些 被选出 的 DALEK 战斗力的成绩之和在不超过所有 DALEK 的战斗力之和的前提下 尽量达到最高。你愣神的功劲，戴沃斯和几个 DALEK 找到了你，并扬言搞不出来就 $\text{kill}$ 了你。

格式

输入格式

第一行有一个整数，表示 DALEK 个数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $a_i$ 表示第 $i$ 个 DALEK 的战斗力。

输出格式

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

样例1

输入样例1

4
100
0
50
100

输出样例1

100

样例解释

所有 DALEK 的战斗力为 $250$，可以选择 $100$ 战斗力的一个 DALEK 派往前线，剩余的防守，不超过所有战斗力的一半。

限制

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