给你一张 3 × n 的矩形表。每个单元格包含一个整数。如果它们共用一侧,您可以从一个牢房移动到另一个牢房。
找到从表格的左上角单元格到右下角单元格的路径,该路径不会访问任何单元格两次,并且该路径的单元格中写入的数字之和是最大可能的。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 表中的列数。
接下来三行每行包含 n 个整数 - 表的描述。第 i 行中的第 j 个数字对应于表格的单元格 aij (- 109 ≤ aij ≤ 109)。
输出
输出从表格的左上角单元格到右下角单元格的路径上的最大数字总和,并且不会访问任何单元格两次。
示例
输入 #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
注意
第一个示例的路径:
第二个示例的路径: