题目描述

你将陆续收到 $N$ 个红包，其中第 $i$ 个红包里有 $A_i$ 元。

对每只红包，你可以选择打开或放弃：

• 如果选择放弃，不会有任何收益
• 如果选择打开，你将获得红包里的钱。此外，如果这只红包是第二个被打开的红包，你将获得双倍的钱，第四、第六个以及所有第偶数个被打开的红包都可以获得双倍的钱。

请问应该选择什么样的策略打开红包使得总收入最大？输出这个最大收入之和。

输入格式

• 第一行：单个整数表示 $N$
• 第二行到第 $N+1$ 行：每行一个整数，表示 $A_1,A_2,\dots,A_N$

输出格式

5
30
10 
40
10
50

220

样例解释 1

30+402+10+502

数据范围

• $30\%$ 的数据，$1 \le N \le 20$
• $60\%$ 的数据，$1 \le N \le 1000$
• $100\%$ 的数据，$1 \le N \le 300,000$
• $1 \le A_i \le 10^9$