P16858 [GKS 2021 #F] Festival

You have just heard about a wonderful festival that will last for $D$ days, numbered from $1$ to $D$. There will be $N$ attractions at the festival. The $i$-th attraction has a happiness rating of $h_i$ and will be available from day $s_i$ until day $e_i$, inclusive. You plan to choose one of the days to attend the festival. On that day, you will choose up to $K$ attractions to ride. Your total happiness will be the sum of happiness ratings of the attractions you chose to ride. What is the maximum total happiness you could achieve?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains the three integers, $D$, $N$ and $K$. The next $N$ lines describe the attractions. The $i$-th line contains $h_i$, $s_i$ and $e_i$.

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the maximum total happiness you could achieve.

In sample test case $1$, the festival lasts $D = 10$ days, there are $N = 4$ attractions, and you can ride up to $K = 2$ attractions. If you choose to attend the festival on the $6$th day, you could ride the first and second attractions for a total happiness of $800 + 1500 = 2300$. Note that you cannot also ride the third attraction, since you may only ride up to $K = 2$ attractions. This is the maximum total happiness you could achieve, so the answer is $2300$. In sample test case $2$, the festival lasts $D = 5$ days, there are $N = 3$ attractions, and you can ride up to $K = 3$ attractions. If you choose to attend the festival on the $3$rd day, you could ride the first and third attractions for a total happiness of $400 + 300 = 700$. This is the maximum total happiness you could achieve, so the answer is $700$. ### Limits $1 \le T \le 100$. $1 \le K \le N$. $1 \le s_i \le e_i \le D$, for all $i$. $1 \le h_i \le 3 \times 10^5$, for all $i$. **Test Set $1$** $1 \le N \le 1000$. $1 \le D \le 1000$. **Test Set $2$** For at most $10$ test cases: - $1 \le N \le 3 \times 10^5$. - $1 \le D \le 3 \times 10^5$. For the remaining cases, $1 \le N, D \le 1000$.