축제

$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$는 얻을 수 있는 총 행복도의 최댓값이다.

• $1 \le T \le 100$.
• $1 \le K \le N$.
• $1 \le s_i \le e_i \le D$, 모든 $i$에 대해.
• $1 \le h_i \le 3 \times 10^5$, 모든 $i$에 대해.

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

6일째에 축제에 참가하면 첫 번째와 두 번째 놀이기구를 타서 총 행복도 $800+1500=2300$을 얻을 수 있다. 최대 $K=2$개의 놀이기구만 탈 수 있으므로 세 번째 놀이기구는 탈 수 없다. 이것이 얻을 수 있는 총 행복도의 최댓값이므로 답은 $2300$이다.

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

3일째에 축제에 참가하면 첫 번째와 세 번째 놀이기구를 타서 총 행복도 $400+300=700$을 얻을 수 있다. 이것이 얻을 수 있는 총 행복도의 최댓값이므로 답은 $700$이다.