P16858 [GKS 2021 #F] Festival

你刚刚听说一个精彩的节日将持续 $D$ 天，编号为 $1$ 到 $D$。节日中有 $N$ 个游乐项目。第 $i$ 个项目有一个快乐值 $h_i$，并且从第 $s_i$ 天到第 $e_i$ 天（包含两端）均可游玩。 你计划选择其中一天去参加节日。在那一天，你最多可以游玩 $K$ 个项目。你的总快乐值等于你所选项目的快乐值之和。 请问你能获得的最大总快乐值是多少？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含三个整数 $D$、$N$ 和 $K$。接下来的 $N$ 行描述每个项目。第 $i$ 行包含 $h_i$、$s_i$ 和 $e_i$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你能获得的最大总快乐值。

在样例 #1 中，节日持续 $D = 10$ 天，有 $N = 4$ 个项目，你最多可以游玩 $K = 2$ 个项目。 如果你选择在第 $6$ 天参加节日，你可以游玩第 $1$ 个和第 $2$ 个项目，总快乐值为 $800 + 1500 = 2300$。注意，你不能再游玩第 $3$ 个项目，因为你最多只能游玩 $K = 2$ 个项目。这是你能获得的最大总快乐值，因此答案为 $2300$。 在样例 #2 中，节日持续 $D = 5$ 天，有 $N = 3$ 个项目，你最多可以游玩 $K = 3$ 个项目。 如果你选择在第 $3$ 天参加节日，你可以游玩第 $1$ 个和第 $3$ 个项目，总快乐值为 $400 + 300 = 700$。这是你能获得的最大总快乐值，因此答案为 $700$。 ### 限制条件 $1 \le T \le 100$。 $1 \le K \le N$。 对于所有 $i$，$1 \le s_i \le e_i \le D$。 对于所有 $i$，$1 \le h_i \le 3 \times 10^5$。 **测试集 1** $1 \le N \le 1000$。 $1 \le D \le 1000$。 **测试集 2** 最多 $10$ 个测试用例满足： - $1 \le N \le 3 \times 10^5$。 - $1 \le D \le 3 \times 10^5$。 其余测试用例满足 $1 \le N, D \le 1000$。 翻译由 DeepSeek V4 Pro 完成