数字钱包

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有 $N$ 个数组，每个数组包含 $M$ 个正整数。第 $i$ 个数组的第 $j$ 个元素为 $A_{i,j}$。

钱包初始金额为 $0$。你需要执行 $M-K+1$ 次操作。在第 $p$ 次操作中：

1. 任意选择一个数组 $x$；
2. 选择一个满足 $p\le y\le p+K-1$ 的下标 $y$；
3. 将 $A_{x,y}$ 加入钱包；
4. 把 $A_{x,y}$ 变为 $0$。

同一个元素即使再次被选择也只能贡献 $0$。求最终能够获得的最大金额。

输入格式

第一行包含三个整数 $N,M,K$。

接下来 $N$ 行，每行包含 $M$ 个整数，表示矩阵 $A$。

输出格式

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

样例输入 1

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

样例输出 1

27

样例输入 2

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

样例输出 2

17

样例输入 3

3 4 3
5 9 10 1
1 3 1 5
2 5 7 2

样例输出 3

19

数据范围

对于所有数据，$1\le N\le10$，$1\le M\le10^5$，$1\le K\le\min(10,M)$，$1\le A_{i,j}\le10^6$。

所有测试点均为独立计分点。