题目描述

你刚刚听说一个精彩的节日将持续 $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$ 是你能获得的最大总快乐值。

2
10 4 2
800 2 8
1500 6 9
200 4 7
400 3 5
5 3 3
400 1 3
500 5 5
300 2 3

Case #1: 2300
Case #2: 700

提示

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