经验加成

题目描述

高桥将依次遭遇 $N$ 只怪物。第 $i$ 只怪物 $(1\le i\le N)$ 的强度为 $A_i$。

对于每只怪物，他可以选择放走它或击败它。

每种行动获得的经验值如下：

• 若放走怪物，获得 $0$ 点经验值。
• 若击败强度为 $X$ 的怪物，获得 $X$ 点经验值。
• 若这是击败的第偶数只怪物（第 2 只、第 4 只、……），额外获得 $X$ 点经验值。

求他从这 $N$ 只怪物中能获得的最大总经验值。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出他所能获得的最大总经验值（作为整数）。

样例

5
1 5 3 2 7

28

若高桥击败第 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
1000000000 1000000000

3000000000

注意答案可能超出 $32$-bit 整数的范围。

数据范围

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