棋

(chess.cpp 1s/512MB)

题目描述

小 W 在玩"超级井字棋"，规则是在一个 $3\times n$ 的棋盘上给每个格子画 X/O，所有格子画完后，每个格子会被染色。具体地，如果当前格子是 X 且它位于连续的三个 X（按行或按列或按对角线排成一线）里，那它会被染成红色；如果当前格子是 O 且它位于连续的三个 O（按行或按列或按对角线排成一线）里，那它会被染成蓝色；否则它会被染成黑色。同时，每个棋盘格都有一个整数权值 $a_{i,j}$，小 W 最终的分数是所有红色格子权值和减去所有蓝色格子权值和。你能告诉小 W 他最终分数的最大值吗？

输入格式

• 第一行包含一个整数 $n$（$1\le n\le 10^3$），表示棋盘的列数。棋盘大小固定为 $3\times n$。
• 接下来 3 行，每行包含 $n$ 个整数，依次给出对应格子的权值 $a_{i,j}$。

输出格式

输出一个整数，表示得分最大值。

输入输出样例 #1

输入 #1

3
1 1 1
1 1 1
1 1 1

输出 #1

9

输入输出样例 #2

输入 #2

4
1 2 3 4
4 -100 2 1
1 3 1 3

输出 #2

119

输入输出样例 #3

输入 #3

10
5  -8   0   3  -6   9  -2   1  -1   7
-7   4  -3   0   6  -4   8  -9   2   5
 1  -5   7  -2   0   6  -8   3  -6  -1 

输出 #3

115

数据范围

对于 $30$ 的数据，$n\le 5$。

另有 $10$ 的数据，$a_{i,j}\ge 0$。

对于 $100$ 的数据，$n\le 10^3,|a_{i,j}|\le 10^9$。