题解

思路推导

每一行的选择数量上限只约束这一行，而整除条件由所有行的余数共同决定。先求出每一行在各种余数下能够取得的最大行内和，再把各行的结果合并即可。

做法

对当前行建立状态 $f[c][r]$，表示选择了 $c$ 个元素且和模 $k$ 为 $r$ 时的最大和。逐个处理该行元素，并按选择数量从大到小更新，保证每个元素至多使用一次。处理完一行后，对所有 $0\le c\le\lfloor m/2\rfloor$ 取最大值，得到该行每种余数的最优和。

再用一维状态 $g[r]$ 表示已处理若干行、总和模 $k$ 为 $r$ 时的最大和。枚举旧余数和当前行余数完成转移。全部行处理完后，答案为 $g[0]$。

正确性证明

行内状态按元素逐个进行“不选或选”转移，并记录选择数量，因此它恰好枚举该行所有不超过数量上限的合法选择；对同余数取最大值得到该行余数最优值。

合并第 $i$ 行时，任意合法全局方案都能唯一拆成前 $i-1$ 行的方案与第 $i$ 行的方案，二者余数相加确定新的总余数。转移枚举了全部这样的组合并取最大值，所以合并后状态保持最优。最终余数为 $0$ 的状态正是题目要求的最大和。

复杂度分析

时间复杂度为 $O(nm^2k+nk^2)$，空间复杂度为 $O(mk)$。