题目描述

如图有一个正方形置物盘，置物盘上有$n × n$个小格子，每个小格子里有数量不等的豆子。对于整个置物盘，我们可以做以下两种操作之一：

操作一：选择置物盘中一行小格子，将这一行小格子中的豆子倒到相邻行中；再选择置物盘中一列小格子，将这一列小格子中的豆子倒到相邻列中。

操作二：将整个置物盘沿顺时针转动一圈。

假设需要做m次操作，请你选择最佳的操作过程，使得做完操作后，将其中的一个格子里的豆子拿出来作为种子时，种子的数量最多。

输入格式

从文件bean.in中读入数据。

总共n+2行。

第一行一个正整数n，代表置物盘上的行数和列数。

第二到n+1行每行n个非负整数$a_{ij}$，代表置物盘上第i行第j列的小格子里有$a_{ij}$个豆子。

第n+2行一个正整数m，代表操作的次数。

输出格式

输出到文件bean.out中。

一个正整数，代表最终拿出来的豆子的数量。

样例 #1

样例输入 #1

2
1 2
3 4
1

样例输出 #1

10

样例 #2

样例输入 #2

6
4 1 2 3 0 1
3 4 0 1 3 0
0 0 1 0 0 0 
0 3 1 0 0 6
6 0 0 1 3 0
0 1 0 3 0 0
1

样例输出 #2

12

提示：

【​样例解释1​】

将第1行的豆子倒到第2行，再将第1列的豆子倒到第2列，此时第2行第2列的豆子数量是10。

【​样例解释2​】

（该样例如题目中的图片所示）将第1行的豆子倒到第2行，再将第1列的豆子倒到第2列，此时第2行第2列的豆子数量是12。

【​数据范围​】

对于$20\%$的数据，$2\leq n \leq 10,1\leq m \leq 10,0\leq a_{ij} \leq 100$。

对于$30\%$的数据，$2\leq n \leq 100,1\leq m \leq 10,0\leq a_{ij} \leq 100$。

对于$100\%$的数据，$2\leq n \leq 10^3,1\leq m \leq 10,0\leq a_{ij} \leq 10^8$。

特殊数据：对于$20\%$的数据，保证m=1。

来源：

2024 西安市信息学算法编程大赛小低组T4、小高组T2