[问题描述]

LG意外收到了一份礼物,是一大堆小球..准确地说,小球共有3种颜色:红黄白.LG决定从这些小球中选出n个来排成一列.如何使得这n个排成一排的小球看着顺眼,这是个问题..

对于连续放置的三个小球,LG都会定义一个”舒适度”.比如他认为三个颜色分别为红红黄的小球连在一起,舒适度为12.

而对于全部n个小球,会有n-2个连续的三个小球.这n-2个组合的舒适度之和,定义为整个序列的舒适度.现在LG想知道,整个序列的舒适度的最大值是多少.

三个小球总共有27种摆法,舒适度分别为:

红红红 4   红红白 12   红红黄 17
红白红 11  红白白 22   红白黄 24
红黄红 27  红黄白 37   红黄黄 30
白红红 6   白红白 18   白红黄 21
白白红 12  白白白 3　　白白黄 16
白黄红 19  白黄白 22   白黄黄 24
黄红红 10  黄红白 13   黄红黄 7
黄白红 6   黄白白 3　　黄白黄 4
黄黄红 7   黄黄白 15   黄黄黄 2

你可以认为,LG手里有无数小球,每个颜色都是.

突然天将画外音！LG说，呃，这样的话万一暴力能做的话不久囧了，于是乎，ben对LG说：“你加一点东东不就行了么。”，“加什么？”LG问道。

于是XX就大胆的改起了题目。 听好下面是XX对题目的赘述。 呃，XX说我有特殊能力，我能给你额外的合适度，你愿意要么？

你不会告诉我你说你不愿意要吧？那也太扯了！

然后XX就叽里咕噜了半天，大概意思就是，如果你在第i个位置放球j的话，XX会给你额外的合适度。

[输入描述]

一个整数,n(3<=n<=100000),表示序列的长度。

接下来有n行，每行三个数。第i行分别表示在第i个位置放红、白、黄时，ben给你的附加合适度。 其他输入不超过40

[输出描述]

一个整数,表示舒适度的最大值。

[样例输入]

3
2 3 4
3 4 2
1 2 1

[样例输出]

43

[数据说明]

30% 3<=n<=10000

100% 3<=n<=100000