样例下载

问题描述

武林中有 M 个人，一共分成 N 个帮派，每个人属于且仅属于一个帮派。

现在要建立武林同盟。

建立武林同盟需要满足以下条件：

• 同一个帮派的所有人是共进退的，要么全部加入武林同盟，要么全不加入武林同盟；

• 加入武林同盟的总人数要大于 M 的一半；

• 如果假设让某个帮派加入武林同盟，将来又要退出武林同盟（其他加入的帮派均不退出），而导致武林同盟中剩余的人数大于 M 的一半，则这个帮派是不允许加入武林同盟的。

武林同盟当然希望能够聚集尽可能多的人。

请你计算最多能有多少人加入武林同盟。

输入

第一行：N

接下来一行：N 个整数，表示各个帮派的人数。可能有的帮派人数为 0。数据保证所有帮派的总人数不超过 100000。

输出

一个整数，表示能加入武林同盟的最多人数。

样例输入

3
1 2 3

样例输出

5

样例解释

假设三个帮派编号分别为 1, 2, 3，总人数 M = 6.

则组建武林同盟的方案有：

（1）帮派 1 和 3，总人数为 4

（2）帮派 2 和 3，总人数为 5

显然，方案 （2） 人数最多。

任何一个帮派都无法单独组建武林同盟，因为人数未超过 M 的一半。同样的原因，帮派 1 和 2 无法组建武林同盟。

帮派 1、2、3 无法组建武林同盟，因为如果帮派 1 加入后再退出，会导致剩余人数超过 M 的一半。

数据范围

50% 的数据，N ≤ 20。

100% 的数据，N ≤ 300。