CF762D.Maximum path

You are given a rectangular table 3 × n. Each cell contains an integer. You can move from one cell to another if they share a side.

Find such path from the upper left cell to the bottom right cell of the table that doesn't visit any of the cells twice, and the sum of numbers written in the cells of this path is maximum possible.

你有一个 $3 \times n$ 的矩形表格，每个格子中包含一个整数。如果两个格子有公共边，则可以从其中一个格子移动到另一个格子。

请找出一条从表格左上角格子到右下角格子的路径，要求该路径不重复经过任意格子，且路径所经过的所有格子中的数字之和尽可能大。

The first line contains an integer n (1 ≤ n ≤ 105) — the number of columns in the table.

Next three lines contain n integers each — the description of the table. The j-th number in the i-th line corresponds to the cell a__ij ( - 109 ≤ a__ij ≤ 109) of the table.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表格的列数。

接下来三行，每行包含 $n$ 个整数 —— 表格的描述。第 $i$ 行中的第 $j$ 个数对应表格中的单元格 $a_{ij}$（$-10^9 \leq a_{ij} \leq 10^9$）。

Output the maximum sum of numbers on a path from the upper left cell to the bottom right cell of the table, that doesn't visit any of the cells twice.

输出从表格左上角单元格到右下角单元格的一条路径上数字的最大和，该路径不能重复访问任何单元格。

The path for the first example:

The path for the second example:

第一个示例的路径：

第二个示例的路径：