题目描述

Patel 博士有 $N$ 叠盘子。每叠有 $K$ 个盘子。每个盘子有一个正的美观值，描述它看起来有多漂亮。

Patel 博士想从中取出恰好 $P$ 个盘子用于今晚的晚餐。如果他想从一叠中取出某个盘子，则必须同时取出该叠中位于它上面的所有盘子。

请帮助 Patel 博士选出 $P$ 个盘子，使得美观值的总和最大。

输入格式

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

输出格式

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

2
2 4 5
10 10 100 30
80 50 10 50
3 2 3
80 80
15 50
20 10

Case #1: 250
Case #2: 180

提示

在样例 #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 完成