회의 일정 잡기

Google에서 회의 일정을 잡는 일은 쉽지 않습니다. Google Calendar가 있어도 Ada는 여전히 어려움을 겪습니다.

Ada는 Google의 소프트웨어 엔지니어입니다. 새 프로젝트의 승인을 받으려면 $\mathbf{N}$명의 Tech Lead 중 적어도 $\mathbf{K}$명을 만나야 합니다.

Ada는 $\mathbf{N}$명 모든 Tech Lead의 일정을 볼 수 있으며, 예정된 회의도 모두 확인할 수 있습니다. 시간축은 연속된 $\mathbf{D}$시간이고, 모든 회의는 정수 끝점을 가지며 $[0, \mathbf{D}]$ 범위 안에 있습니다. 예정된 회의는 같은 사람의 것이라도 서로 겹칠 수 있습니다.

Ada는 $[0, \mathbf{D}]$ 안에서 시작과 끝이 정수인 $\mathbf{X}$시간짜리 회의를 잡아야 합니다. 적어도 $\mathbf{K}$명의 Tech Lead가 회의 전 시간 동안 참석할 수 있어야 하므로, 그들의 일정이 회의 시간 내내 완전히 비어 있어야 합니다.

이런 시간대가 없을 수도 있습니다. 그런 경우 Ada는 일부 Tech Lead에게 기존 회의를 취소해 달라고 설득해야 합니다.

Ada가 적어도 $\mathbf{K}$명의 Tech Lead와 만날 수 있도록, 취소해야 하는 예정 회의의 최소 개수를 구하세요.

첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어집니다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어집니다.

각 테스트 케이스의 첫 줄에는 정수 네 개 $\mathbf{N}$, $\mathbf{K}$, $\mathbf{X}$, $\mathbf{D}$가 주어집니다. $\mathbf{N}$은 Tech Lead의 수, $\mathbf{K}$는 Ada가 만나야 하는 Tech Lead의 최소 수, $\mathbf{X}$는 잡아야 할 회의의 길이, $\mathbf{D}$는 범위 $[0, \mathbf{D}]$의 상한입니다. 어떤 회의도 $\mathbf{D}$ 이후에 끝날 수 없습니다.

둘째 줄에는 예정된 회의의 수 $\mathbf{M}$이 주어집니다.

이어지는 $\mathbf{M}$개의 줄에는 정수 세 개 $\mathbf{P_i}$, $\mathbf{L_i}$, $\mathbf{R_i}$가 주어집니다. Tech Lead $\mathbf{P_i}$에게 열린 구간 $(\mathbf{L_i}, \mathbf{R_i})$의 예정 회의가 있다는 뜻이며, 끝점은 포함하지 않습니다. 같은 시작과 끝 시간을 가진 회의가 있더라도 $\mathbf{M}$개의 회의는 모두 독립적입니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력합니다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Ada가 적어도 $\mathbf{K}$명의 Tech Lead와 $\mathbf{X}$시간짜리 회의를 잡기 위해 취소해야 하는 예정 회의의 최소 개수입니다.

시간축은 구간 $[0, \mathbf{D}]$, 즉 연속된 $\mathbf{D}$시간으로 볼 수 있습니다. $\mathbf{D}$는 24보다 클 수 있습니다.

회의 $(L, R)$은 $L$번째 시간의 시작에 시작하여 $R$번째 시간의 시작에 끝나며, 그 사이 전체 시간을 빈틈없이 덮습니다. 끝점은 구간에 포함되지 않습니다. Ada의 새 회의는 Tech Lead의 다른 회의와 맞닿을 수 있습니다. 다른 회의가 끝나자마자 시작할 수도 있고, 다른 회의가 시작하자마자 끝날 수도 있으며, 둘 다일 수도 있습니다. 취소되지 않은 다른 회의가 Ada의 회의와 어느 순간이라도 겹치면, 그 Tech Lead는 Ada의 회의에 참석할 수 없습니다.