题目描述

你是一位超级农夫，拥有一些蔬菜种子和一片无限大的农场。事实上，你不仅是一位农夫，还秘密地是一位超级程序员！作为一名超级程序员，你希望利用你的编程技能最大化农场的利润。

由于你每天的精力有限，每天最多可以种植 $X$ 颗种子。起初，你有 $N$ 种蔬菜种子。第 $i$ 种蔬菜的种子数量为 $Q_i$，并且该种蔬菜的每颗种子从种植之日起需要 $L_i$ 天才能成熟。一旦成熟，你可以将其卖出获得 $V_i$ 美元。假设收获和销售蔬菜不消耗精力或时间。此外，你的农场无限大，因此生长的蔬菜不会互相挤占。

请注意，尽管你的农场面积无限，但你能种植种子的天数却是有限的。暖季只持续 $D$ 天，之后严酷的冬季到来。任何尚未成熟的蔬菜会立即死亡，无法转化为利润。未种植的剩余种子也无法转化为利润。

作为超级农夫和超级程序员，你想出一个完美的种植计划来最大化你的利润。请计算你将获得的总利润。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含三个整数 $D$、$N$ 和 $X$：分别表示暖季的天数、初始拥有的蔬菜种子种类数，以及每天最多可以种植的种子数量。

接下来的 $N$ 行描述每种种子。第 $i$ 行包含三个整数 $Q_i$、$L_i$ 和 $V_i$：分别表示该种蔬菜的种子数量、所需成熟天数，以及每株成熟作物的价值。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是通过优化种植计划能获得的最大金额。

2
5 4 1
1 2 3
1 3 10
1 4 5
1 2 2
5 1 1
1 1 1

Case #1: 18
Case #2: 1

1
5 3 4
5 2 3
2 3 10
2 4 5

Case #1: 45

提示

在样例 #1 中，有 $D = 5$ 天，$N = 4$ 种蔬菜，每天最多种植 $X = 1$ 颗种子。假设这 $4$ 种蔬菜分别是菠菜、南瓜、胡萝卜和卷心菜，我们有：

• 菠菜需要 $2$ 天生长，每株价值 $3$ 美元，初始有 $1$ 颗菠菜种子。
• 南瓜需要 $3$ 天生长，每株价值 $10$ 美元，初始有 $1$ 颗南瓜种子。
• 胡萝卜需要 $4$ 天生长，每株价值 $5$ 美元，初始有 $1$ 颗胡萝卜种子。
• 卷心菜需要 $2$ 天生长，每株价值 $2$ 美元，初始有 $1$ 颗卷心菜种子。

你能获得的最大利润为 $18$ 美元。你可以使用以下种植计划：

• 第 $1$ 天：种植 $1$ 颗胡萝卜
• 第 $2$ 天：种植 $1$ 颗南瓜
• 第 $3$ 天：种植 $1$ 颗菠菜
• 第 $4$ 天：种植 $1$ 颗卷心菜
• 第 $5$ 天：什么都不做

按照该计划，蔬菜成熟并转化为利润的情况如下：

• 第 $1$ 天：无收获
• 第 $2$ 天：无收获
• 第 $3$ 天：无收获
• 第 $4$ 天：无收获
• 第 $5$ 天：收获 $1$ 株菠菜、$1$ 株南瓜和 $1$ 株胡萝卜，赚得 $18$ 美元

注意，卷心菜本应在第 $6$ 天成熟，但由于冬季到来实际上会死亡。

在附加样例 #1 中，有 $D = 5$ 天，$N = 3$ 种蔬菜，每天最多种植 $X = 4$ 颗种子。假设这 $3$ 种蔬菜分别是菠菜、南瓜和胡萝卜，我们有：

• 菠菜需要 $2$ 天生长，每株价值 $3$ 美元，初始有 $5$ 颗菠菜种子。
• 南瓜需要 $3$ 天生长，每株价值 $10$ 美元，初始有 $2$ 颗南瓜种子。
• 胡萝卜需要 $4$ 天生长，每株价值 $5$ 美元，初始有 $2$ 颗胡萝卜种子。

你能获得的最大利润为 $45$ 美元。你可以使用以下种植计划：

• 第 $1$ 天：种植 $1$ 颗南瓜、$2$ 颗胡萝卜和 $1$ 颗菠菜
• 第 $2$ 天：种植 $2$ 颗菠菜和 $1$ 颗南瓜
• 第 $3$ 天：种植 $2$ 颗菠菜
• 第 $4$ 天：什么都不做
• 第 $5$ 天：什么都不做

按照该计划，蔬菜成熟并转化为利润的情况如下：

• 第 $1$ 天：无收获
• 第 $2$ 天：无收获
• 第 $3$ 天：收获 $1$ 株菠菜，赚得 $3$ 美元
• 第 $4$ 天：收获 $2$ 株菠菜和 $1$ 株南瓜，赚得 $16$ 美元
• 第 $5$ 天：收获 $2$ 株菠菜、$1$ 株南瓜和 $2$ 株胡萝卜，赚得 $26$ 美元

限制条件

内存限制：$1$ GB。

$1 \le T \le 100$。

对于所有 $i$，$1 \le V_i \le 10^6$。

对于所有 $i$，$1 \le L_i \le D$。

测试集 1

$2 \le D \le 1000$。

$1 \le N \le 15$。

$X = 1$。

对于所有 $i$，$Q_i = 1$。

测试集 2

$2 \le D \le 10^5$。

$1 \le N \le 10^5$。

$1 \le X \le 10^9$。

对于所有 $i$，$1 \le Q_i \le 10^6$。

测试集 3

$2 \le D \le 10^{12}$。

$1 \le N \le 10^5$。

$1 \le X \le 10^9$。

对于所有 $i$，$1 \le Q_i \le 10^6$。

$D \times X \le 10^{18}$。

翻译由 DeepSeek V4 Pro 完成