题目内容

给出一个边长为 $n$ 的立方体网格。网格中每个小方块对应一个整数权值。你需要从立方体中选择一条长度为 $n$ 的直线。

允许选择的直线方向包括：沿坐标轴方向（分别与 $x$、$y$ 或 $z$ 轴平行的整行/整列/整柱）；沿任一坐标平面的面对角线方向（例如在 $xOy$ 平面中，每一步 $x$ 与 $y$ 同时加 $\pm1$、$z$ 不变；其余两个平面同理）；沿空间对角线方向（每一步 $x$、$y$、$z$ 同时加 $\pm1$）。

形式化地，设方向步长为 $(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$，都有 $0 \le x_0 + kd_x, y_0 + kd_y, z_0 + kd_z \le n-1$，从而得到一条恰好经过 $n$ 个小方块的直线。请计算在所有允许方向与所有合法起点中，经过的小方块权值之和的最大值。

输入描述

在一行上输入一个整数 $n$（$1 \le n \le 100$），表示立方体的边长。

此后 $n \times n$ 行，按“层”的顺序给出权值。对于第 $k$ 个“层”，输入 $n$ 行：第 $i$ 行输入 $n$ 个整数 $a_{i,0,k}, a_{i,1,k}, \dots, a_{i,n-1,k}$（$-10^6 \le a_{i,j,k} \le 10^6$），表示第 $k$ 层第 $i$ 行第 $j$ 列小方块的权值。共计输入 $n \times n \times n$ 个整数。

输出描述

输出一个整数，表示所有允许方向与所有合法起点中，经过的小方块权值之和的最大值。

样例1

输入

2
1 2
3 4
5 6
7 8

输出

15

说明

立方体边长 $n = 2$。第 $0$ 层 $a_{\cdot,\cdot,0}$ 的两行为 $1, 2$ 和 $3, 4$；第 $1$ 层 $a_{\cdot,\cdot,1}$ 的两行为 $5, 6$ 和 $7, 8$。

枚举所有方向所有合法起点，几条候选直线权值和：沿 $x$ 方向 $(0,1,1) \to (1,1,1)$ 为 $6 + 8 = 14$；沿 $y$ 方向 $(1,0,1) \to (1,1,1)$ 为 $7 + 8 = 15$；沿 $z$ 方向 $(1,1,0) \to (1,1,1)$ 为 $4 + 8 = 12$；沿 $xy$ 面对角 $(0,0,1) \to (1,1,1)$ 为 $5 + 8 = 13$；沿空间对角 $(0,0,0) \to (1,1,1)$ 为 $1 + 8 = 9$。最大值为 $15$。