题目内容

物流园区有一座边长为 $n$ 的立方立体仓，货位用三维坐标 $(x, y, z)$ 标识，各维取值均为 0 到 $n-1$。每个货位记录一个整数盘点分（可正可负）。仓储主管计划沿一条恰好穿过 $n$ 个货位的直线通道做一次连贯扫描，希望沿途盘点分之和尽可能大。

通道方向可以与坐标轴平行，也可以沿任一坐标平面的面对角线，还可以沿体对角线。形式化地，方向步长为 $(d_x, d_y, d_z)$，其中 $d_x, d_y, d_z \in \{-1, 0, 1\}$ 且不全为 0。选定方向后，起点 $(x_0, y_0, z_0)$ 必须满足：对所有 $k = 0, 1, \dots, n-1$，坐标 $x_0 + k d_x$、$y_0 + k d_y$、$z_0 + k d_z$ 都落在 $[0, n-1]$ 内。请在所有允许方向与所有合法起点中，求盘点分之和的最大值。

约束：边长不超过 100，每个货位盘点分的绝对值不超过 1000000。

输入描述

第一行一个整数 $n$，表示立体仓的边长。 此后按层给出盘点分：共 $n$ 层，第 $k$ 层有 $n$ 行，第 $i$ 行有 $n$ 个整数，表示该层第 $i$ 行各列货位的盘点分。共计 $n \times n \times n$ 个整数。 保证 $1 \le n \le 100$，每个盘点分的绝对值不超过 1000000。

输出描述

输出一个整数，表示所有合法直线通道中盘点分之和的最大值。

样例1

输入

1
-7

输出

-7

说明

边长 $n=`1`$，晶格只有一个格点，能量为 -7。唯一合法直线就是该点本身，答案为 -7。

样例2

输入

2
9 -2
4 0
3 8
1 5

输出

17

说明

边长为 2。第 0 层两行为 9,-2 与 4,0，第 1 层两行为 3,8 与 1,5。

方向 $(d_x,d_y,d_z)=(0,1,1)$、起点 $(0,0,0)$ 经过能量 9 与 8，和为 17。枚举全部合法直线后这是最大值。

样例3

输入

2
0 0
0 0
0 0
0 1

输出

1

说明

除一点能量为 1 外其余为 0。任意经过该点的长度为 2 的直线能量和至多为 1，答案为 1。