题目描述

电玩城新进了 $n$ 台抓娃娃机，每台机器中依次放有一排 $m$ 个娃娃。用 $a_{i,j}$ 表示徐老师对第 $i$ 台娃娃机中第 $j$ 个娃娃的喜爱度。

老板给出一个整数 $k$，徐老师一共进行 $m-k+1$ 次选择。对于第 $i$ 次选择，徐老师只能从任意娃娃机中选择一个编号位于 $[i,i+k-1]$ 的、尚未被拿走的娃娃，也可以选择不拿娃娃。

请计算徐老师最多可以获得的喜爱度总和。

输入格式

本题采用文件读写。

• 读入文件名：toy.in
• 写出文件名：toy.out

第一行包含三个整数 $n,m,k$。

接下来 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}$。

输出格式

输出一个整数，表示最大喜爱度总和。

样例

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

27

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

13

数据范围与提示

• 对于 $30\%$ 的数据，$1\le n,m\le5$。
• 对于 $60\%$ 的数据，$1\le n\le10,1\le m\le1000$。
• 对于另外 $10\%$ 的数据，$k=1$。
• 对于全部数据，$1\le n\le10,1\le m\le10^5,1\le k\le\min(10,m),0\le |a_{i,j}|\le10^9$。