题目描述

果农 小z 有一台自动化苹果收割机，最开始是​ 关闭的（即无法工作）​。他有 $n$ 棵苹果树，第 $i$ 棵树上有 $a_i$ 个苹果。他将以任意顺序访问所有苹果树，每棵树恰好访问一次。

小z 的自动化苹果收割机在访问每一棵苹果树之前，会检查该树上的苹果数量是 奇数 还是 ​偶数​。

• 如果是奇数，收割机 ​切换自身状态​（如果当前是关闭状态，就打开；如果是打开状态，就关闭）；
• 如果是偶数，收割机不会发生任何变化。

随后，

• 如果收割机处于​开启状态​，小z 会将该棵树上的所有苹果都收割掉；
• 如果收割机是​关闭状态​，他只是单纯访问该树，不收割任何苹果。

请你帮 小z 计算：如果他以最优顺序访问这 $n$ 棵苹果树，他​最多可以收割多少个苹果​？

数据范围:

对于 $60$%的数据： $1≤n≤100,1≤a_i≤10^5$。

对于 $100$%的数据： $1≤n≤10^5,1≤a_i≤10^9$。

输入格式

第一行输入一个整数 $n$，表示苹果树的数量。

接下来一行输入 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$，表示每棵苹果树上的苹果数。

输出格式

输出一个整数，表示 小z 在最优访问顺序下最多可以收割的苹果数量。

4
4 2 1 6

13

3
6 8 10

0

5
5 6 7 8 9

30

提示

对于第一个测试用例：

小z 可以先访问第三棵树（上面有 $1$ 个苹果），此时收割机会开启。之后无论访问顺序如何，收割机始终保持开启状态，因此 小z 可以收割所有苹果，总数为 $4+2+1+6=13$。

对于第三个测试用例：

小z 可以按如下顺序访问苹果树：第 $5$ 棵 → 第 $4$ 棵 → 第 $2$ 棵 → 第 $1$ 棵 → 第 $3$ 棵。这样收割机状态最优，总共可以收割 $30$ 个苹果