#1147. [202403月赛] 谁最多利事

[202403月赛] 谁最多利事

背景

过去的一个月是农历新年,小方小块小鸟度过了一个有趣的传统中国年。他们从生肖、对联等传统习俗里积累了不少文化知识;过年的糖果、食物让他们大饱口福;还有大家最喜欢的烟花、炮竹,绚丽多彩又热闹非凡。可惜很快的,年就过完了,他们已经在期待下一个新年的到来。这天,他们在分享自己的新年见闻,又展开了很多有意思的对话。

描述

经过你的帮助,小方小块小鸟已经完成了所住街区的「利事地图」,现在他们想要知道,居住在某户的小朋友如果从家出发去周围的邻居家里「逗利事」,最多能收到的「利事」金额是多少。他们发现了,虽然广府文化里面,只要向陌生人说新年祝福,也是可以领到「利事」的,但还是会不好意思的呀。一般来说,他们都对附近的邻居比较熟悉。现在规定,某位小朋友只跟离家东、南、西、北四个方向相隔不超过kk户的人家熟悉,我们将kk称为「社牛指数」。同时规定,小朋友只能向熟悉的邻居「逗利事」。问,整个街区里哪一户人家的小朋友能收到的「利事」总金额最高,是多少?注意,自己家的利事在大年初一已经收过了,所以不能再收哦。

说明,如下图街区,当k=2k=2时,家在3行4列(x标记)的小朋友熟悉的邻居用o标记。

.ooooo..
.ooooo..
.ooxoo..
.ooooo..
.ooooo..
........
........
........
........

输入输出格式

输入

第一行输入三个整数 rowrow, colcol, kk,分别表示街区的行数、列数和「熟悉」邻居的范围。 ( 5row,col,k10015 ≤ row , col, k ≤ 1001 )

接下来 rowrow 行,每行为colcol个以空格分割分的非负整数,表示每一户的红包金额amountamount。 ( 0amount200 ≤ amount ≤ 20)

输出

两行,第一行为以空格分割的两个正整数xyx y,表示居住在x行y列的小朋友能领到最高金额的「利事」; ( 注意,行、列均从1开始计算,即第一行为1 );

第二行为一个整数amountamount,为最高的「利事」金额。

样例

4 5 1
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
3 4
112

样例一说明

显然,当「社牛指数」k=1时,居住在第3行4列的小朋友可以向以下邻居「逗利事」

  • 2行3列 2行4列 2行5列
  • 3行3列 3行5列
  • 4行3列 4行4列 4行5列

共计112112