Digital Wallet
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2300
Tags: dp, greedy

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!

Input format:
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 format:
Output an integer representing the maximum total money that can be earned.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
3 3 1
10 4 2
8 1 9
4 8 2

Example output:
27

Example input:
3 3 2
5 9 4
1 3 1
2 8 7

Example output:
17

Editorial:
First, notice that since the initial value of all elements are positive, it is always optimal to always choose an element that has not been chosen before in each operation.
Let's look at the $$$N$$$ arrays as a grid of $$$N$$$ rows and $$$M$$$ columns. We can solve this problem by iterating each column from left to right and using dynamic programming. Define the following:
• $$$\text{dp}[i][j]$$$: the maximum money Chaneka can earn by only taking the elements of the first $$$i$$$ columns in $$$j$$$ operations.
When we iterate a new column $$$i$$$, we can choose to choose $$$c$$$ elements in that column for some value $$$c$$$ ($$$0\leq c\leq N$$$). If we choose to choose $$$c$$$ elements in that column, it is always the most optimal to choose the $$$c$$$ biggest elements in that column.
Notice that if we only consider the first $$$i$$$ columns, in the optimal strategy, we must do a minimum of $$$i-K+1$$$ operations and a maximum of $$$i$$$ operations. So there are only a maximum of $$$K$$$ different values of $$$j$$$ we need to consider when calculating all values of $$$\text{dp}[i][j]$$$ for each new column $$$i$$$. For each $$$\text{dp}[i][j]$$$, there are only $$$N+1$$$ possibilities for the number of elements we choose in column $$$i$$$, and each of them can be handled in $$$O(1)$$$.
Time complexity: $$$O(NMK)$$$