23077번 - 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 hihi, $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.

제한

• 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 (8점)

시간 제한: 20 초

• 1ドル \le N\le 1000$.
• 1ドル \le D \le 1000$.

Test Set 2 (10점)

시간 제한: 90 초

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$.

힌트

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 6th 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 3rd 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ドル$.