[Baltic2008]Elect

有 $N$ 个政党准备组成联合内阁，每个政党拥有一定数量的席位。设所有政党的席位总数为 $S$，需要选择若干政党组成联合内阁，并满足以下条件：

• 联合内阁拥有的席位数严格大于 $S$ 的一半；
• 联合内阁中的任何一个政党退出后，其余政党的席位数均不再大于 $S$ 的一半。

在满足上述条件的所有方案中，求联合内阁最多能够拥有的席位数。

输入格式

第一行包含一个整数 $N$，表示政党的数量。

第二行包含 $N$ 个非负整数 $a_i$，其中 $a_i$ 表示第 $i$ 个政党拥有的席位数。

输出格式

输出一个整数，表示满足条件的联合内阁最多能够拥有的席位数。

样例输入

4
1 3 2 4

样例输出

7

数据范围

• $1\le N\le 300$；
• $a_i\ge 0$；
• $1\le \sum_{i=1}^{N}a_i\le 10^5$。

来源与许可

本题为 Baltic 2008 试题「Elect」，题面与测试数据整理自 BZOJ。

样例 1

输入

4
1 3 2 4

输出

7