题目描述

小\(A\)正在做寒假作业呢！突然，他的损友小\(B\)来到了他的家，告诉小\(A\)他发明了一种格子游戏。

这种格子游戏可以看作一个\(3*n\)的格子。每个格子都有自己的分数。

小\(A\)一开始可以站在第\(1\)行的任意一列。小\(A\)每次可以选择向右边跳，向右上方跳，向右下方跳。当然，如果他在最上面或者最下面，那当然不能继续往上跳或往下跳。

小A最后可以在\((1,n),(2,n),(3,n)\)（注：指坐标）中的任意一点结束。问如何设计路线，使得小\(A\)获得的分数最大，战胜小\(B\)。

输入格式

第一行一个整数，\(N\)。

第二到四行，每行\(N\)个整数，表示这个格子游戏每个格子的分数。

输出格式

仅有一行一个整数，表示可获得的最大分数。

输入样例#1:

3
1 2 -1
-4 8 -2
-7 -11 -23

输出样例#1:

8

样例说明:

样例中的跳法如下图所示。

小A一开始站在第\(1\)行，他的线路是\((1,1)->(2,2)->(1,3)\)，总的得分为\(1+8+(-1)=8\)。

数据范围

有\(2\)组的数据，\(N\le 100\)。

另有\(4\)组的数据，\(N\le 1000\)。

其中\(4\)组的数据，没有负分数。

全\(6\)组的数据，\(N\le 1000\)，其余数字均\(\le 10^6\)。

测试点分值: \(1\)至\(5\)点\(16pts\)每点，\(6\)点\(20pts\)。