疫情爆发后，丛雨带着她的 $3$ 个侍卫管理灯塔。

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

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

丛雨通过空间魔法得知了之后 $m$ 天内每天每座灯塔路过的商船数目。丛雨希望之后 $m$ 天路过点亮的灯塔的商船总数尽可能大。她请你求这个最大的总数。

输入格式

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

输出格式

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

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)$。