CF1866D Digital Wallet

有 $N$ 个数组，每个数组有 $M$ 个正整数元素，第 $i$ 个数组的第 $j$ 个元素为 $A_{i,j}$。 起初，Chaneka 的电子钱包中有 $0$ 元。给定一个整数 $K$。Chaneka 将进行 $M-K+1$ 次操作。在第 $p$ 次操作中，Chaneka 按如下步骤进行： 1. 选择任意一个数组。假设选择了第 $x$ 个数组。 2. 在该数组中选择一个下标 $y$，满足 $p \leq y \leq p+K-1$。 3. 将 $A_{x, y}$ 的值加入钱包的总金额中。 4. 将 $A_{x, y}$ 的值变为 $0$。 请你求出最多可以获得多少总金额。

第一行包含三个整数 $N$、$M$ 和 $K$（$1 \leq N \leq 10$；$1 \leq M \leq 10^5$；$1 \leq K \leq \min(10, M)$），分别表示数组的个数、每个数组的长度和操作的约束常数。 接下来的 $N$ 行，每行包含 $M$ 个整数 $A_{i,1}, A_{i,2}, \ldots, A_{i,M}$（$1 \leq A_{i,j} \leq 10^6$），表示第 $i$ 个数组的元素。

输出一个整数，表示最多可以获得的总金额。

在第一个样例中，以下是一种最优策略的操作顺序： 1. 选择元素 $A_{1, 1}$，其值为 $10$。 2. 选择元素 $A_{3, 2}$，其值为 $8$。 3. 选择元素 $A_{2, 3}$，其值为 $9$。 因此总共获得的金额为 $10+8+9=27$。 在第二个样例中，以下是一种最优策略的操作顺序： 1. 选择元素 $A_{3, 2}$，其值为 $8$。 2. 选择元素 $A_{1, 2}$，其值为 $9$。 因此总共获得的金额为 $8+9=17$。 在第三个样例中，以下是一种最优策略的操作顺序： 1. 选择元素 $A_{1, 3}$，其值为 $10$。 2. 选择元素 $A_{1, 2}$，其值为 $9$。 因此总共获得的金额为 $10+9=19$。 由 ChatGPT 4.1 翻译