You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

输入格式（light.in）

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

输出格式（light.out）

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

输入样例

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

输出样例

44

数据范围

对于 $10\%$ 的数据，满足 $k = n$ 。 对于 $30\%$ 的数据，满足 $n, m \leq 10$ 。 对于 $60\%$ 的数据，满足 $n, m \leq 1000$ 。 对于 $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)$ 。