CF1866D Digital Wallet

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.

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