该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个 $n\times m$ 的整数矩阵，你需要找出一个 “十”字形区域，使得这个区域中所有元素的和最大。

“十”字的定义如下：

选择一个中心格子 $(i,j)$；向上下左右最多扩展 $k$ 步（但不能越界）； 包含的格子为：中心格子、上至 $k$ 格、下至 $k$ 格、左至 $k$ 格、右至 $k$ 格（共最多 $4k+1$ 个格子）；

请你求出，所有可能的“十”字区域中，最大的元素和是多少。

输入格式

第一行包含三个整数 $n,m,k (1≤n,m≤200，0≤k<min(n,m))$ 接下来 $n$ 行，每行 $m$ 个整数 $a_{i,j}(-10^4\le a_{i,j}\le10^4)$

输出格式

输出一个整数，表示最大“十”字区域的和。

3 3 1
1 2 3
4 5 6
7 8 9

29

5 5 0
1 2 3 4 5
5 4 3 2 1
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3

5

数据规模与约定

对于 $100\%$ 的数据，$1≤n,m≤200，0≤k<min(n,m)$，$-10^4\le a_{i,j}\le10^4$。

解释说明

• 样例1

选择中心为 (3,2)，即数字 8。其十字形区域包括：

• 中心：8
• 上：5
• 下：无（0）
• 左：7
• 右：9

总和为 $8 + 5 + 0 + 7 + 9 = 29$