题目背景

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\) 均为偶数。