AT_jsc2026_final_d Debt Cancellation

给定一个长度为 $N$ 的整数序列 $a=(a_1,a_2,\ldots,a_N)$。初始时，$a=(0,0,\ldots,0)$。 接下来依次进行 $Q$ 次更新。在第 $i$ 次更新时，对于所有 $j=1,2,\ldots,N$，将 $X_{i,j}$ 加到 $a_j$ 上。 在每次更新的所有加法操作完成后，你可以选择是否进行一次**归零操作**： - 对所有 $j=1,2,\ldots,N$，将 $a_j$ 替换为 $\max(a_j,0)$。 给定整数 $M$。对于每个 $k=1,2,\ldots,M$，请你求出，当恰好进行了 $k$ 次归零操作时，最终 $\sum_{i=1}^N a_i$ 可能取得的最大值。

输入将以下列格式由标准输入给出。 > $N$ $Q$ $M$ $X_{1,1}$ $X_{1,2}$ $\ldots$ $X_{1,N}$ $X_{2,1}$ $X_{2,2}$ $\ldots$ $X_{2,N}$ > $\vdots$ > $X_{Q,1}$ $X_{Q,2}$ $\ldots$ $X_{Q,N}$

对于每个 $k=1,2,\ldots,M$，依次输出答案，数之间用空格隔开。

### 样例解释 1 当 $k=1$ 时，在第 $2$ 次更新后进行归零操作，此时 $a$ 的变化如下： - 第 $1$ 次更新后：$a=(-2,5,-1)$ - 第 $2$ 次更新后：$a=(-5,2,-7)$，此时执行归零操作，$a=(0,2,0)$ - 第 $3$ 次更新后：$a=(5,4,-1)$ - 第 $4$ 次更新后：$a=(-2,8,4)$ 最终 $\sum_{i=1}^N a_i = 10$。 当 $k=2$ 时，最优是在第 $3,4$ 次更新后分别进行归零操作。 ### 数据范围 - $1 \le N \le 10$ - $1 \le Q \le 10^4$ - $1 \le M \le \min(Q,1000)$ - $-10^9 \le X_{i,j} \le 10^9$ - 输入的所有值均为整数。 由 ChatGPT 5 翻译