#967. 希蒙品酒

希蒙品酒

希蒙品酒

题目描述

希蒙刚刚与萌萌打赌赢得了一间在赛码社区的大客厅。今天,他来到这个大客厅欣赏他的奖品。蒙蒙摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。

令希蒙高兴的是,瓶子中的酒都有不同的味道。蒙蒙说道:“你可以喝尽可能多的酒,但是一旦打开酒盖你就必须把它喝完,喝完一瓶后把它放回原处。还有一件最重要的事,你必须从左至右依次喝,并且不能连续喝三瓶,不然会给你带来坏运气。”

现在可怜的希蒙站在酒吧前努力的想着,他到底应该喝哪几瓶才能使喝的酒最多呢?请帮助他找出他应该喝的酒瓶号,因为思考让他感到不安。

输入格式

第一行一个整数N,有N个酒瓶。N<=700接下有N行,第I+1行的数字代表酒瓶I中酒的体积。

输出格式

一个数字,喝的酒的最大总体积。

样例 #1

样例输入 #1

6
6
10
13
9
8
1

样例输出 #1

33