题目描述

马里奥玩一款游戏，游戏里有 $n$ 个豆豆，第 $i$ 个豆豆拥有 $a_i$ 积分。

马里奥选择吃或者不吃某个豆豆，如果他选择吃，将获得这个豆豆的积分。

游戏有一个奖励机制，如果吃到的豆豆数是 $3$ 的倍数，将获得一倍的额外奖励, 即吃到第 $3,6,9,\dots$ 个豆时，将获得一倍额外奖励。

例如：$7$ 个豆豆 ，对应积分是 3 2 1 2 3 3 4 , 他可以选择吃第 $1,2,4,5,6,7$ 个豆豆 ，吃第 $4$ 个和第 $7$ 个豆豆将获得一倍的额外奖励积分 ， 将获得 $3+2+2*2+3+3+4*2=23$ 的积分。

在知道所有豆豆积分的情况下，请计算马里奥可能获得的最高积分。

输入格式

第一行，一个整数 $n$

第二行，$n$ 个整数，第 $i$ 个整数表示 $a_i$

输出格式

一个整数，表示马里奥可能获得的最高积分。

7
3 2 1 2 3 3 4

23

20
1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 5 4 3 2 1

49

20
774976392 458446214 732149174 169515255 614436801 339464701 499348511 120146640 44543255 238021562 569803441 723648969 8585552 356605575 163526585 165392434 635799991 147586026 204886007 140629383

9827790033

下发文件：down

数据规模与约定

所有数据满足：$1 \leq n \leq 2\times 10^5, 1 \leq a_i \leq 10^9$

$Subtask1$ : $1\leq n \leq 20$, $20$ 分

$Subtask2$ : $1 \leq n \leq 10^3$, $30$ 分

$Subtask3$ : $1 \leq n \leq 2\times 10^5$, $50$ 分

注意数据溢出。