AT_abc369_d [ABC369D] Bonus EXP

题目描述

高桥君遇到了 $N$ 只怪物，依次遇到每一只怪物，第 $i$ 只怪物的强度为 $A_i$。

高桥君可以选择对每只怪物是放走还是击败。
高桥君通过以下的方式获得经验值：

• 如果选择放走怪物，获得的经验值为 $0$。
• 如果击败强度为 $X$ 的怪物，他可以获得 $X$ 的经验值。但是，如果这是他第偶数次击败怪物（即第 $2$ 次、第 $4$ 次、……），他将额外获得 $X$ 的经验值。

请计算高桥君通过击败怪物可以获得的最大总经验值。

输入格式

输入从标准输入中读取，格式如下：

$N$ $A_1$ $A_2$ $A_N$

输出格式

输出高桥君可能获得的最大总经验值。

输入输出样例 #1

输入 #1

5
1 5 3 2 7

输出 #1

28

输入输出样例 #2

输入 #2

2
1000000000 1000000000

输出 #2

3000000000

说明/提示

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 输入的所有数值均为整数

样例解释 1

在击败第 1、2、3、5 只怪物并放走第 4 只怪物时，高桥君可以按如下方式获得经验值：

• 击败强度为 $A_1=1$ 的怪物，获得 $1$ 的经验值。
• 击败强度为 $A_2=5$ 的怪物，获得 $5$ 的经验值。这是高桥君第 2 次击败怪物，因此额外获得 $5$ 的经验值。
• 击败强度为 $A_3=3$ 的怪物，获得 $3$ 的经验值。
• 放走第 4 只怪物，高桥君不获得经验值。
• 击败强度为 $A_5=7$ 的怪物，获得 $7$ 的经验值。这是高桥君第 4 次击败怪物，因此额外获得 $7$ 的经验值。

因此，总共获得的经验值为 $1+(5+5)+3+0+(7+7)=28$。
由于无论如何行动，总经验值都不会超过 $28$，所以输出 $28$。

请注意，如果击败所有怪物，获得的经验值为 $1+(5+5)+3+(2+2)+7=25$。

样例解释 2

请注意，答案可能会超过 32 位整数型的范围。