Maximum path

题意翻译

## **题目描述** 你被给了一个3*n的矩形表格。每个小格含有一个整数。如果两个格子有共享的边，你可以从一个格子移到另一个格子。 找到如下从左上角的格子到右下角的格子的路径，这条路径不能重复参观同一个格子，并且路径中的格子中的数字的和应该是可能的最大值。 ------------ ## **输入格式**## 第一行包含一个整数n（1<=n<=10^5）,代表矩形表格的纵列列数。 下三行每行有n个数，是对表格对描述。第i行第j个数对应格子aij(-10^9<=aij<=10^9)。 ## 输出格式 输出从表格的左上格到右下格的路径上的最大数字总和，不会重复访问同一个格子

题目描述

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.

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ) — 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} $ ( $ -10^{9}<=a_{ij}<=10^{9} $ ) of the table.

输出格式

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.

输入输出样例

输入样例 #1

3
1 1 1
1 -1 1
1 1 1

输出样例 #1

7

输入样例 #2

5
10 10 10 -1 -1
-1 10 10 10 10
-1 10 10 10 10

输出样例 #2

110

说明

The path for the first example: The path for the second example: