/ WHOJ / 题库 /

准备

准备

题目背景

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