Migrated from Lutece 3223 游园会

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

为迎接 4202 年新年的到来，营造轻松、愉快的校园氛围，增进学院学生之间的交流，增强学生的归属感。以“XXXX，XXXX”为主题，组织开展内容丰富、形式多样、富有特色的迎新年游园会。通过游园会活动，让学生更深入地了解校园环境和文化，感受学院的关心、关怀和温暖。通过这次活动，使学生们能够将更好融入校园生活，为未来的学习和成长打下坚实的基础。

为了综合素质实践混分和劳育学时放松心情，你报名参与了游园会活动。 游园会的规则如下：

1. 活动场地被分为 $3*N$ 个点位，每个点位都有一个游戏。
2. 每个游戏会根据你的表现登记分数 $x$ ，分数为整数且可能为负数。
3. 游玩结束当前点位后你可以向上、下、左、右任意一个方向移动去玩下一个点位的游戏，但不能走出场地范围。
4. 为维持场地秩序和提高游玩效率，不能向已游玩过的点位移动，且不能路过点位但不玩这个点位的游戏。
5. 从场地左上角的点位开始游玩，在场地右下角的点位结束，只有结束游戏且不违反上述规则才算活动分数有效。

你通过关系在活动前打探到了各点位具体的游戏项目，同时也预测出自己在每个点位能拿到的分数。现在你想知道，在活动中你最多能拿多少分。

Input

第一行输入一个整数 $N$ —— 活动场地在横向被划分的点位数量。 接下来 $3$ 行，分别输入 $N$ 个数表示每个点位的预期得分。

Output

输出一个整数，表示预期能得到的最大分数。

Samples

5
-1 1 1 -1 -1
-1 1 1 1 1
-1 1 1 1 -1

7

4
0 -1 2 2
-2 0 0 1
1 -2 2 0

6

Constraints

$1\le N \le 10^5, -10^9\le x \le 10^9$

Note

对于样例1，存在一条得分最高路径 $(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (3,3) \rightarrow (3,4) \rightarrow (2,4) \rightarrow (2,5) \rightarrow (3,5)$。

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming