Background

土拨鼠牛牛上初三了, 他最喜欢的就是妹子和数字三了

Description

这一天, 他玩起了"小三"游戏, 游戏规则如下, 现在有$n$组妹子,每组妹子有$a_i$个, 可以选择一组或几组的妹子, 如果要选择某一组, 必须把妹子全部抱走. 规则要求, 你选择的妹子数量必须是$3$的倍数, 现在牛牛想知道, 最多可以选走多少妹子?

Format

Input

第1行一个整数$n$.

第2行有n个整数, 表示每组妹子的个数$a_i$.

Output

输出一个整数, 表示答案, 答案要求尽可能多的选择妹子, 同时必须是3的整数倍.

Samples

7
3 8 1 9 10 4 6

36

样例解释

选择 3+8+10+9+6=36，36 为 3 的倍数且可以发现这是能选择的最大的总和。

Limitation

1s, 1024KiB for each test case.

$1\leq n\leq 10^6,\ 1\leq a_i\leq 10^9$。