D. 王后(sword.cpp) 内存限制：256 MiB 时间限制：1000 ms 标准输入输出 题目类型：传统 评测方式：文本比较 题目描述 疫病爆发后，王后带着她的 3 个侍卫管理灯塔。

海上有 n 个灯塔,编号从 1 到 n。每份燃料能够支持灯塔点亮两天。

王后每天早上需要给编号相邻的 k 个灯塔清理掉旧的燃料残渣(如果有未用完的 燃料也会一并清理掉)并添加一份新燃料。

王后通过空间魔法得知了之后 m 天内 每天每座灯塔路过的商船数目。

王后希望之后 m 天路过点亮的灯塔的商船总数尽可能大。她请你求这个最大的总数。

输入格式 第一行包含三个整数 n、m 和 k (1≤n≤10000, 1≤m≤10000,1≤n*m≤500000 1≤k≤min（n,50）) 接下来的 m 行每行包含 n 个整数。

第 i+1 行中的第 j 个整数 t 是在第 i 天第 j 个灯塔路过的商船数量(0≤t≤1000)

输出格式 输出一个整数，分别代表路径的起点和终点。

样例 输入 #1 4 3 2 1 0 2 3 4 5 6 0 0 7 8 9 输出 #1 44 数据范围与提示 第一天点亮 3，4

第二天点亮 1，2

第三天点亮 3，4

对于 10% 的数据，满足 k=n。

对于 30% 的数据，满足 n,m ≤ 10。

对于 60% 的数据，满足 n,m ≤ 1000。

对于 100% 的数据，满足 1≤n≤10000, 1≤m≤10000,1≤n*m≤500000,1≤k≤ min(n,50)