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.

很不幸，Guan 的钱包一块钱都不剩了！为了赚钱，他看上了 $N$ 支股票以及这些股票未来 $M$ 天的价格。设第 $i$ 支股票第 $j$ 天的价格为 $A_{i,j}$。

Guan 有一项魔法：他可以将某个价格对应的数字记录下来，然后立刻获得等价值的电子币！不过，Guan 的这个魔法会受到某个给定参数 $K$ 的影响。具体来说，他会使用恰好 $M-K+1$ 次魔法，对于第 $p$ 次魔法：

1. Guan 会选择任意一支股票。假设他选择的是第 $x$ 支股票；
2. Guan 会选择一个正整数 $y$，要求 $p \le y \le p + K - 1$；
3. Guan 会将 $A_{x,y}$ 记录下来，然后立刻获得 $A_{x,y}$ 电子币。之后，$A_{x,y}$ 会变为 $0$。

Guan 想要知道：他一共最多能赚多少电子币？

输入格式

第一行三个正整数 $N,M,K$，含义见题面。

接下来输入 $N$ 行，每一行 $M$ 个正整数，表示 $A_{i,j}$。

输出格式

输出一行一个整数，表示 Chaneka 最多能赚到的电子币。

3 3 1
10 4 2
8 1 9
4 8 2

27

Guan 会依次选择 $A_{1,1}, A_{3,2}, A_{2,3}$，一共能赚 $10+8+9=27$ 电子币。

提示

• 对于 $30\%$ 的数据，$1 \le N, M \le 5$

• 对于 $60\%$ 的数据，$1 \le N \le 10, 1 \le M \le 1000$

• 对于另 $10\%$ 的数据，$K = 1$

• 对于 $100\%$ 的数据，$1\le N \le 10, 1\le M \le 10^5, 1\le K \le \min(10, M), 1\le A_{i,j} \le 10^6$