#4358. 灯塔

灯塔

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

输入格式(light.in)

第一行包含三个整数 nnmmkk 。 接下来的 mm 行每行包含 nn 个整数。第 i+1i+1 行中的第 jj 个整数 tt是在第 ii 天第 jj 个灯塔路过的商船数量。

输出格式(light.out)

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

输入样例

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

输出样例

44

数据范围

对于 10%10\% 的数据,满足 k=nk = n 。 对于 30%30\% 的数据,满足 n,m10n, m \leq 10 。 对于 60%60\% 的数据,满足 n,m1000n, m \leq 1000 。 对于 100%100\% 的数据,满足 $1 \leq n \leq 10000,1 \leq m \leq 10000,0 \leq t \leq 1000, 1 \leq n*m \leq 500000, 1 \leq k \leq min(n,50)$ 。