题目描述

三十六方，必为大统！------小张

小张是一个热爱方阵的男孩子，他正在参加埃湖大学组织的军训。训练场上的方阵为若干个 $n\times n$ 的矩形，其中第 $i$ 行第 $j$ 列的同学的身高为 $h_{i,j}$。小方想设计一个函数来描述每个方阵的特征。他定义一个方阵的“方值”如下：

• 对于一个方阵，小张首先会尝试将方阵分割成若干个均匀（大小相等）的子方阵。他希望分割的方阵数量尽可能少（但要大于 $1$），且每个子方阵的边长大于 $1$。然后该方阵的“方值”即为分割出的子方阵的“方值”和。
• 如果一个方阵不能被按上述方式分割，则方阵的“方值”为方阵中学生所有学生身高的最大值。

例如，对于一个 $9\times 9$ 的方阵，小方会将其分割成 $9$ 个 $3\times 3$ 的方阵，而对于 $3\times 3$ 的方阵无法继续分割。

现在，小张想知道对于一个给定的方阵，它的“方值”为多少。

输入格式

第一行一个整数 $n(1\le n\le 2022)$，表示方阵的大小；

接下来 $n$ 行，每行 $n$ 个整数，描述方阵中每名同学的身高 $h_{i,j}\ (1\le h_{i,j}\le 2022)$。

输出格式

输出一行一个整数，表示给定方阵的“方值”。

4
1 1 4 5
1 4 1 9
1 9 8 1
6 6 6 6

30