灯塔 （light）

题目描述

疫情爆发后，丛雨带着她的 3 个侍卫管理灯塔。 海上有 n 个灯塔,编号从 1 到 n。每份燃料能够支持灯塔点亮两天。丛 雨每天早上需要给编号相邻的 k 个灯塔清理掉旧的燃料残渣(如果有 未用完的燃料也会一并清理掉)并添加一份新燃料。丛雨通过空间魔 法得知了之后 m 天内每天每座灯塔路过的商船数目。丛雨希望之后 m 天路过点亮的灯塔的商船总数尽可能大。她请你求这个最大的总 数。

输入格式

第一行包含三个整数 n、m 和 k 。 接下来的 m 行每行包含 n 个整数。第 i+1 行中的第 j 个整数 t 是在第 i 天第 j 个灯塔路过的商船数量。

输出格式

输出一个整数，表示最大的总数。

样例 #1

样例输入 #1

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

样例输出 #1

44

提示

数据范围

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

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

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

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