该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近很喜欢电玩城里的抓娃娃机，这天他发现电玩城里新进了 $n$ 台特殊的娃娃机，编号 $1 \sim n$

在每台娃娃机中，依次放有一排一共 $m$ 个娃娃，序号依次为 $1 \sim m$

而由于娃娃机中的娃娃款式各不相同，徐老师对每种款式的娃娃喜爱度也不同

为了方便表示，我们用 $a_{i,j}$ 来表示徐老师对第 $i$ 个娃娃机中编号为 $j$ 的娃娃的喜爱度

老师发现徐老师天天在电玩城里抓娃娃，但是总抓不起来！

于是老板决定对徐老师进行一次感恩大酬宾活动，让徐老师任选喜欢的娃娃带走，但是在这之前，老板决定考考徐老师

老板会给定一个整数 $k$，徐老师一共进行 $m - k + 1$ 次选择，每次徐老师可以选择一个娃娃带走

但是对于第 $i$ 次选择，徐老师只能选择序号在 $[i, i + k - 1]$ 范围内的娃娃拿走（娃娃机编号不限，并且在拿走这个娃娃后，这个位置就空了，不再有娃娃）

现在徐老师想知道自己最多可以获得多少喜爱度？

输入格式

输入一行包含三个整数 $n,m,k$ 含义如题

接下来 $n$ 行，每行 $m$ 个整数 $a_{i,j}$ 表示编号为 $i$ 的娃娃机中序号为 $j$ 的娃娃的喜爱度

输出格式

输出一个答案，表示徐老师最多能获得的喜爱度之和。

数据范围

对于 $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$

样例输入1

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

样例输出1

27

样例解释1

徐老师会依次选择第 $1$ 台娃娃机中的每个娃娃

样例输入2

5 5 3
1 2 3 4 5
1 2 3 5 1
1 2 1 5 2
1 2 3 4 5
1 1 1 1 1

样例输出2

13

样例解释2

其中一种选择方案是：

1. 第一次选择第 $1$ 台娃娃机中序号为 $3$ 的娃娃，喜爱度为 $3$
2. 第二次选择第 $2$ 台娃娃机中序号为 $4$ 的娃娃，喜爱度为 $5$
3. 第三次选择第 $3$ 台娃娃机中序号为 $4$ 的娃娃，喜爱度为 $5$