Description

奇奇在研究完藏宝图之后，他感到他需要一个团队和他一起前行。于是他便拿出了许多美味的水果，打算邀请他最好的朋友一起来品尝，并且加入他组建的勇敢的冒险团。所以他需要一个帮手，去帮他找到最美味的水果。于是他找来了著名的美食家。美食家提出了一个要求，如果奇奇答应，那么他帮助奇奇找到最美味的水果。美食家的要求如下：他会将找到的美味水果分成 n 堆，每堆的重量不一定，奇奇只能选择其中不超过一半堆数的水果。聪明的小伙伴，你们可以帮助奇奇尽可能多的获得水果去宴请他的朋友吗？

Format

Input

输入数据有多组。输入一个整数n（0 < n <= 1,000）代表有n堆水果,接下来一行输入n个整数,（每个整数范围不超过1000000），代表每堆水果的重量。

Output

每组输出占一行，输出奇奇最多可以获得的水果的重量。

Samples

5
1 2 3 4 5

9

Hint