题目描述

疫病爆发后，王后带着她的 $3$ 个侍卫管理灯塔。

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

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

王后通过空间魔法得知了之后 $m$ 天内每天每座灯塔路过的商船数目，她希望之后 $m$ 天内路过点亮的灯塔的商船总数尽可能大。

请你求出总数的最大值。

输入格式

第一行包含三个整数 $n,m,k$，分别表示灯塔数量，天数，王后添加燃料的范围。

接下来的 $m$ 行，每行包含 $n$ 个整数，第 $i$ 行第 $j$ 个整数为 $a_{i,j}$，表示第 $i$ 天路过第 $j$ 个灯塔的商船数目。

输出格式

输出一个整数，表示路过点亮的灯塔的商船总数的最大值。

样例

输入

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

输出

44

样例解释

第一天点亮 $3,4$。

第二天点亮 $1,2$。

第三天点亮 $3,4$。

数据范围

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

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

对于 $60\%$ 的数据，满足 $n,m ≤ 10^3$。

对于 $100\%$ 的数据，满足 $1≤n,m≤10^4$，$1≤n \times m≤5\times 10^5$，$1≤k≤\min(n,50)$。