Digital Wallet

给定一个 $n \times m$ 的矩阵，执行 $m - k + 1$ 轮： 第 $i$ 轮在 $i$ ~ $i + k -1$ 列中选择一个数，每个数只能被选择一次。 问选择的总和最大是多少。 其中 $n,k \le 10$，$m \le 1e5$。

There are $ N $ arrays, each array has $ M $ positive integer elements The $ j $ -th element of the $ i $ -th array is $ A_{i,j} $ . Initially, Chaneka's digital wallet contains $ 0 $ money. Given an integer $ K $ . Chaneka will do $ M-K+1 $ operations. In the $ p $ -th operation, Chaneka does the following procedure: 1. Choose any array. Let's say Chaneka chooses the $ x $ -th array. 2. Choose an index $ y $ in that array such that $ p \leq y \leq p+K-1 $ . 3. Add the value of $ A_{x, y} $ to the total money in the wallet. 4. Change the value of $ A_{x, y} $ into $ 0 $ . Determine the maximum total money that can be earned!

The first line contains three integers $ N $ , $ M $ , and $ K $ ( $ 1 \leq N \leq 10 $ ; $ 1 \leq M \leq 10^5 $ ; $ 1 \leq K \leq \min(10, M) $ ) — the number of arrays, the size of each array, and the constant that describes the operation constraints. The $ i $ -th of the next $ N $ lines contains $ M $ integers $ A_{i,1}, A_{i,2}, \ldots, A_{i,M} $ ( $ 1 \leq A_{i,j} \leq 10^6 $ ) — the elements of the $ i $ -th array.

Output an integer representing the maximum total money that can be earned.

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

27

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

17

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

19

In the first example, the following is a sequence of operations of one optimal strategy: 1. Choosing element $ A_{1, 1} $ with a value of $ 10 $ . 2. Choosing element $ A_{3, 2} $ with a value of $ 8 $ . 3. Choosing element $ A_{2, 3} $ with a value of $ 9 $ . So the total money earned is $ 10+8+9=27 $ . In the second example, the following is a sequence of operations of one optimal strategy: 1. Choosing element $ A_{3, 2} $ with a value of $ 8 $ . 2. Choosing element $ A_{1, 2} $ with a value of $ 9 $ . So the total money earned is $ 8+9=17 $ . In the third example, the following is a sequence of operations of one optimal strategy: 1. Choosing element $ A_{1, 3} $ with a value of $ 10 $ . 2. Choosing element $ A_{1, 2} $ with a value of $ 9 $ . So the total money earned is $ 10+9=19 $ .