P16748 [GKS 2020 #A] Plates

Patel 博士有 $N$ 叠盘子。每叠有 $K$ 个盘子。每个盘子有一个正的**美观值**，描述它看起来有多漂亮。 Patel 博士想从中取出恰好 $P$ 个盘子用于今晚的晚餐。如果他想从一叠中取出某个盘子，则必须同时取出该叠中位于它上面的所有盘子。 请帮助 Patel 博士选出 $P$ 个盘子，使得美观值的总和最大。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$、$K$ 和 $P$。随后 $N$ 行，第 $i$ 行包含 $K$ 个整数，按从上到下的顺序描述每叠盘子的美观值。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Patel 博士能选出的最大美观值总和。

在样例 #1 中，Patel 博士需要取出 $P=5$ 个盘子： - 他从第一叠中取最上面的 $3$ 个盘子（$10+10+100=120$）。 - 他从第二叠中取最上面的 $2$ 个盘子（$80+50=130$）。 总美观值之和为 $250$。 在样例 #2 中，Patel 博士需要取出 $P=3$ 个盘子： - 他从第一叠中取最上面的 $2$ 个盘子（$80+80=160$）。 - 他从第二叠中不取盘子。 - 他从第三叠中取最上面的 $1$ 个盘子（$20$）。 总美观值之和为 $180$。 ### 限制条件 $1 \le T \le 100$。 $1 \le K \le 30$。 $1 \le P \le N \times K$。 美观值在 $1$ 到 $100$ 之间（包含两端）。 **测试集 1** $1 \le N \le 3$。 **测试集 2** $1 \le N \le 50$。 翻译由 DeepSeek V4 Pro 完成