시간 제한메모리 제한제출정답맞은 사람정답 비율
서브태스크 참고 (추가 시간 없음) 1024 MB644100.000%

## 문제

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

## 예제 입력 1

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


## 예제 출력 1

Case #1: 2300
Case #2: 700


## 힌트

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

## 채점 및 기타 정보

• 예제는 채점하지 않는다.