あなたの蛙は旅立っています

题号：NC15233
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

あなたの蛙は旅立っています！

你的蛙正在考虑它应该按怎样的路线去旅行。这些景点可以抽象为

个镶嵌着的六边形。每个景点

都有一个快乐度

。蛙蛙想要决定一条路线，使得路线上的景点快乐度之和最大。而你的蛙蛙又是一只不走回头路的蛙，所以它每次只能朝远处走。

比如，上图就是一个例子。蛙蛙会从最上方的黄色六边形出发，每次只能走到下方的直接相邻的三个六边形中（边界上可能只有一个或两个直接相邻的六边形），这样一直走到最下方的黄色六边形中。这一段旅程总的快乐值定义为途径的景点的快乐值之和。蛙蛙想要找到一条快乐值最大的路径开始它的旅行。
你的蛙蛙已经迫不及待了，赶紧したく然后かんりょう吧！

输入描述:

输入第一行一个数  ， 表示大六边形的边长（边长定义为大六边形的一条边上小六边形的个数）。 
接下去  行，每行  个整数  ，描述大六边形中的一行景点的快乐度。具体可以看题目描述中的图。图中，颜色相同的并且在同一行的数字将会作为输入中的一行。
其中：
第 1 ~ n 行：第 i 行 i 个数
第 n + 1 ~ 3n - 2 行：
第 n + 1, n + 3, ..., 3n - 3 行 n - 1 个数
第 n + 2, n + 4, ..., 3n - 2 行 n 个数
第 3n - 1 ~ 4n - 3 行：
分别是 n - 1, n - 2, ..., 1 个数

输出描述:

输出共一行，一个整数，表示最大能得到的快乐值。

示例1

输入

复制

输出

复制

题目描述

输入描述:

输出描述:

输入

输出

说明

备注: