축제

당신은 $\mathbf{D}$일 동안 열리는 멋진 축제에 대해 방금 들었다. 날짜에는 $1$부터 $\mathbf{D}$까지 번호가 매겨져 있다. 축제에는 $\mathbf{N}$개의 놀이기구가 있다. $i$번째 놀이기구의 행복도는 $\mathbf{h_i}$이며, $\mathbf{s_i}$일부터 $\mathbf{e_i}$일까지 양 끝 날짜를 포함하여 이용할 수 있다.

당신은 축제에 참가할 날 중 하나를 선택할 계획이다. 그날 최대 $\mathbf{K}$개의 놀이기구를 골라 탄다. 총 행복도는 타기로 선택한 놀이기구들의 행복도 합이다.

달성할 수 있는 최대 총 행복도는 얼마인가?

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{K} \le \mathbf{N}$. 모든 $i$에 대해 $1 \le \mathbf{s_i} \le \mathbf{e_i} \le \mathbf{D}$. 모든 $i$에 대해 $1 \le \mathbf{h_i} \le 3 \times 10^5$.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 1000$. $1 \le \mathbf{D} \le 1000$.

테스트 세트 2

시간 제한: 90초. 최대 $10$개의 테스트 케이스에 대해 다음이 성립한다:

• $1 \le \mathbf{N} \le 3 \times 10^5$.

• $1 \le \mathbf{D} \le 3 \times 10^5$.

나머지 케이스에서는 $1 \le \mathbf{N}, \mathbf{D} \le 1000$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 세 정수 $\mathbf{D}$, $\mathbf{N}$, $\mathbf{K}$가 주어진다. 다음 $\mathbf{N}$개의 줄에는 놀이기구에 대한 설명이 주어진다. $i$번째 줄에는 $\mathbf{h_i}$, $\mathbf{s_i}$, $\mathbf{e_i}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며, 1부터 시작한다. $y$는 달성할 수 있는 최대 총 행복도이다.

예제 테스트 케이스 1에서 축제는 $\mathbf{D} = 10$일 동안 열리고, 놀이기구는 $\mathbf{N} = 4$개이며, 최대 $\mathbf{K} = 2$개의 놀이기구를 탈 수 있다.

축제의 6th 날에 참가하기로 선택하면 첫 번째와 두 번째 놀이기구를 타서 총 행복도 $800 + 1500 = 2300$를 얻을 수 있다. 최대 $\mathbf{K} = 2$개의 놀이기구만 탈 수 있으므로 세 번째 놀이기구까지 탈 수는 없다는 점에 유의하라. 이는 달성할 수 있는 최대 총 행복도이므로 답은 $2300$이다.

예제 테스트 케이스 2에서 축제는 $\mathbf{D} = 5$일 동안 열리고, 놀이기구는 $\mathbf{N} = 3$개이며, 최대 $\mathbf{K} = 3$개의 놀이기구를 탈 수 있다.

축제의 3rd 날에 참가하기로 선택하면 첫 번째와 세 번째 놀이기구를 타서 총 행복도 $400 + 300 = 700$를 얻을 수 있다. 이는 달성할 수 있는 최대 총 행복도이므로 답은 $700$이다.