题目描述

现在学校里要选择学生会，现在开始投票，候选人都能获得一定票数。

现在我们要求：

1）学生会成员的获得的票数总数必须大于等于所有候选人的获得票数累加和的一半。

2）如果某个人假设进入学生会会，但是他退出后学生会成员的获得票的总数还满足条件1，我们认为这个人是不能入选学生会。

现在问，学生会会获得的票数总数最多是多少？

输入格式

第一行一个N，表示班里有N个人。

第二行N个数，表示每个人获得的票数。

输出格式

一个整数，学生会会获得的票数最大值。

样例数据

input

4
1 3 2 4

output

7

input

6
1 1 2 2 3 3

output

7

总票数为10，学生会由获得3票的2号和4票的4号组成，其余两人不能入选学生会。

数据规模与约定

100% 数据保证 $1 \leq N \leq 300,票数总数不超过10^6$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$