问题描述

有N张卡片，第i（1 ≤ i ≤ N）张卡片上写着整数$A_i$。游戏爱好者的兄弟姐妹想要用这些卡片玩游戏。

• 首先将所有卡片放在桌子上，使卡片上写的整数可见。
• 在自己的回合，玩家从桌子上选择一张卡片拿走。
• 一直轮流进行，直到桌子上没有卡片为止。
• 最后，玩家拿到的卡片上写的整数之和作为玩家的得分。

当两个人都尽可能地提高自己的得分时，先手的得分将是多少？

输入

输入通过标准输入给出，格式如下：

$N$

$A_1$ $A_2$ ... $A_N$

• 第1行包含整数$N$，表示卡片的数量$N$（$1 ≤ N ≤ 1000$）。
• 第2行包含$N$个整数，以空格分隔，表示每张卡片上写的整数$A_1$，$A_2$，...，$A_N$。其中第$i$（$1 ≤ i ≤ N$）个整数$A_i$（$1 ≤ A_i ≤ 1000$）表示第$i$张卡片上写的整数。

输出

输出先手的得分，换行结束。

输入示例1

2
400 628

输出示例1

628

在这个示例中，游戏进行如下：

• 先手拿走第2张卡片。
• 后手拿走第1张卡片。

此时，先手的得分为628，后手的得分为400。

输入示例2

5
2 5 9 6 5

输出示例2

16

在这个示例中，游戏进行如下：

• 先手拿走第3张卡片。
• 后手拿走第4张卡片。
• 先手拿走第2张卡片。
• 后手拿走第5张卡片。
• 先手拿走第1张卡片。

此时，先手的得分为16，后手的得分为11。