J17 习题-4 控制内阁

题目描述

佩奇在玩模拟人生，她想控制的整个内阁！ 游戏里共有 $N$ 个政党，每个党都有自己的席位数，现在要从中选若干个政党组成一个联合内阁。佩奇希望找出一种方案，组成的内阁席位数要大于总数的一半，并且使得联合内阁的席位数越多越好。 联合内阁有规定：如果某个政党退出内阁后，内阁的其它党的席位仍大于总席位数的一半，则这个政党被称为是多余的，这是不允许的。

输入格式

第一行给出有政党的总数 $n$； 第二行给出每个政党的席位数，总席位数小于等于 $100000$ 。

输出格式

一个整数，表示佩奇需要控制的方案中最多能占多少个席位。

样例输入

4
1 3 2 4

样例输出

7

样例分析

选择第二个和第四个政党组成内阁。

数据范围

对于$100\%$ 的数据：$1 \le n \le 300$。