库克船长和他的团队被岛上的土著人俘虏了。为了不被吃掉，探险队员们必须给土著人一些财宝。事实证明，船长拥有 $n$ 件财宝。

土著部落的首领同意放走船长和他的团队，前提是他们必须交出至少一半的财宝。在首领眼中，所有的财宝看起来都很诱人，所以他同意接受任何财宝，只要数量达到总数的一半即可。

但实际上，每件财宝都有库克所知的特定价值。第 $i$ 件财宝的价值为 $a_i$。请帮助船长决定应该给首领哪些财宝，使得他自己留下的财宝总价值最大。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 1000$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$)。

输出格式

输出一个整数，表示船长在交给土著人至少一半财宝后，自己能留下的财宝的最大总价值。

样例

输入 1

6
2 4 1 3 3 5

输出 1

12

说明

在给出的样例中，库克可以将价值为 1、2 和 3 的财宝交给首领，而将价值为 3、4 和 5 的财宝留给自己。它们的总价值为 $3 + 4 + 5 = 12$。