#arc038a. [arc038_a]カードと兄妹

[arc038_a]カードと兄妹

问题描述

有N张卡片,第i(1 ≤ i ≤ N)张卡片上写着整数AiA_i。游戏爱好者的兄弟姐妹想要用这些卡片玩游戏。

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

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


输入

输入通过标准输入给出,格式如下:

NN

A1A_1 A2A_2 ... ANA_N

  • 第1行包含整数NN,表示卡片的数量NN1N10001 ≤ N ≤ 1000)。
  • 第2行包含NN个整数,以空格分隔,表示每张卡片上写的整数A1A_1A2A_2,...,ANA_N。其中第ii1iN1 ≤ i ≤ N)个整数AiA_i1Ai10001 ≤ A_i ≤ 1000)表示第ii张卡片上写的整数。

输出

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


输入示例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。