The old song declares “Go ahead and hate your neighbor”, and the residents of Onetinville have taken those words to heart. Every resident hates his next-door neighbors on both sides. Nobody is willing to live farther away from the town’s well than his neighbors, so the town has been arranged in a big circle around the well. Unfortunately, the town’s well is in disrepair and needs to be restored. You have been hired to collect donations for the Save Our Well fund.

### 输入格式

Each of the town’s residents is willing to donate a certain amount, as specified in the vector donations, which is listed in clockwise order around the well. However, nobody is willing to contribute to a fund to which his neighbor has also contributed. Next-door neighbors are always listed consecutively in donations, except that the first and last entries in donations are also for next-door neighbors.

-donations contains between 2 and 40 elements, inclusive.

-Each element in donations is between 1 and 1000, inclusive.

### 输出格式

You must calculate and return the maximum amount of donations that can be collected.

### 样例

Input
6
10 3 2 5 7 8
/*
40
94 40 49 65 21 21 106 80 92 81 679 4 61 6 237 12 72 74 29 95 265 35 47 1 61 397 52 72 37 51 1 81 45 435 7 36 57 86 81 72
*/

Output
19
The maximum donation is 19, achieved by 10+2+7. It would be better to take 10+5+8 except that the 10 and 8 donations are from neighbors.
/*
2926
*/


17 人解决，27 人已尝试。

21 份提交通过，共有 50 份提交。

5.2 EMB 奖励。