회의 일정 잡기

Google에서 회의 일정을 잡는 것은 쉬운 일이 아니다. Google Calendar의 도움을 받아도 Ada는 여전히 큰 어려움을 겪고 있다!

Ada는 Google에서 Software Engineer(으)로 일하며, 자신의 새 프로젝트에 대한 승인을 받아야 한다. 승인을 받으려면 $\mathbf{N}$ Tech Leads 중 적어도 $\mathbf{K}$명과 만나야 한다.

Ada는 $\mathbf{N}$ Tech Leads 전원의 달력을 볼 수 있다. 각 Tech Lead에 대해 Ada는 예정된 모든 회의를 볼 수 있다. 이 문제의 시간대는 연속된 $\mathbf{D}$시간으로 볼 수 있으며, 모든 회의는 양 끝이 모두 정수인 $[0, \mathbf{D}]$시간 범위 안에 있다. 같은 사람의 회의라도 예정된 회의끼리 겹칠 수 있다(Google 사람들은 이러기로 악명이 높다!).

Ada는 양 끝이 모두 정수인 $[0, \mathbf{D}]$시간의 구간에 $\mathbf{X}$시간 동안 진행되는 회의를 잡아야 한다. $\mathbf{N}$ Tech Leads 중 적어도 $\mathbf{K}$명은 회의 전체에 참석해야 한다. 즉, 이들의 달력은 회의가 진행되는 내내 완전히 비어 있어야 한다.

안타깝게도 이미 그러한 $\mathbf{X}$시간짜리 회의를 잡을 시간대를 찾는 것이 불가능할 수도 있다. 이 경우 Ada는 일부 Tech Leads에게 기존 회의를 취소하도록 설득해야 한다.

Ada가 적어도 $\mathbf{K}$명의 Tech Leads과 만날 수 있도록 취소해야 하는 예정된 회의의 최소 개수는 얼마인가?

제한

시간 제한: 40초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{P_i} \le \mathbf{N}$. 모든 $i$에 대해 $0 \le \mathbf{L_i} < \mathbf{R_i} \le \mathbf{D}$.

테스트 세트 1

$1 \le \mathbf{X} \le \mathbf{D} \le 8$. $1 \le \mathbf{K} \le \mathbf{N} \le 10$. $0 \le \mathbf{M} \le 20$.

테스트 세트 2

$1 \le \mathbf{X} \le \mathbf{D} \le 10^5$. $1 \le \mathbf{K} \le \mathbf{N} \le 10^5$. $0 \le \mathbf{M} \le 10^5$.

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

각 테스트 케이스의 첫 번째 줄에는 네 정수 $\mathbf{N}$, $\mathbf{K}$, $\mathbf{X}$, $\mathbf{D}$가 주어진다. $\mathbf{N}$는 Tech Leads의 수를 나타내고, $\mathbf{K}$는 만나야 하는 Tech Leads Ada의 최소 인원수이며, $\mathbf{X}$는 잡아야 하는 회의의 길이이고, $\mathbf{D}$는 문제의 시간대를 나타내는 $[0, \mathbf{D}]$시간 범위의 상한이다. 어떤 회의도 $\mathbf{D}$ 이후에 끝날 수 없다.

각 테스트 케이스의 두 번째 줄에는 예정된 회의의 수를 나타내는 정수 $\mathbf{M}$이 주어진다.

이어서 $\mathbf{M}$개의 줄이 주어진다. 이 중 $i$번째 줄에는 세 정수 $\mathbf{P_i}$, $\mathbf{L_i}$, $\mathbf{R_i}$가 주어진다. 이 수들은 Tech Lead $\mathbf{P_i}$에게 $\mathbf{L_i}$시와 $\mathbf{R_i}$시 사이에 양 끝점을 포함하지 않는 예정된 회의가 있음을 나타낸다. 즉, 이 회의는 $(\mathbf{L_i}, \mathbf{R_i})$ 구간으로 볼 수 있다.

테스트 케이스에 있는 $\mathbf{M}$개의 회의는 일부 회의의 시작 시각과 종료 시각이 같더라도 모두 서로 독립적이라는 점에 유의한다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Ada가 적어도 $\mathbf{K}$명의 Tech Leads과 $\mathbf{X}$시간 동안 진행되는 회의를 잡을 수 있도록 취소해야 하는 예정된 회의의 최소 개수이다.

Time Format에 관한 참고

이 문제의 시간대는 $[0, \mathbf{D}]$ 구간으로 볼 수 있다. 즉, $\mathbf{D}$가 $24$보다 클 수 있는 연속된 $\mathbf{D}$시간이다.

$(L, R)$ 구간의 회의는 $L$번째 시간의 시작에 회의를 시작하고 $R$번째 시간의 시작에 끝내며, 그 사이의 전체 시간대를 빈틈없이 포함한다는 의미이다. 즉, 구간은 연속적이다. $(L, R)$ 구간에는 양 끝점이 포함되지 않는다. Ada가 잡은 회의에 참석하는 테크 리드의 경우, Ada의 새 회의는 취소되지 않은 다른 회의와 경계를 맞댈 수 있다. 즉, 다른 회의가 끝나는 바로 그때 시작하거나, 다른 회의가 시작하는 바로 그때 끝나거나, 둘 다일 수 있다. 취소되지 않은 다른 회의가 어느 한 시점이라도 Ada의 회의와 겹치면 해당 테크 리드는 Ada의 회의에 참석할 수 없다.

더 명확한 이해를 위해 예제 테스트 케이스의 설명을 참고한다.

세 예제 테스트 케이스 모두에서 예정된 회의는 다음과 같다.

예제 케이스 #1에서 Ada는 적어도 두 명의 Tech Leads과 두 시간 동안 진행되는 회의를 잡아야 한다. Ada는 Tech Leads $#1$ 및 $#3$과 함께 $1$시와 $3$시 사이에 그러한 회의를 잡을 수 있다. 이 경우 기존 회의를 취소할 필요가 없다.

예제 케이스 #2에서 Ada는 세 명의 Tech Leads 모두와 두 시간 동안 진행되는 회의를 잡아야 한다. Ada는 $[0, 2]$ 구간에 그러한 회의를 잡을 수 있으며, 이를 위해 회의 $2$과 $4$을 취소해야 한다. 또 다른 방법은 $[1, 3]$ 구간에 회의를 잡는 것이다. 두 방법 모두 회의 두 개를 취소해야 하며, 이는 가능한 최소 개수이다.

예제 케이스 #3에서 Ada는 적어도 두 명의 Tech Leads과 세 시간 동안 진행되는 회의를 잡아야 한다. Ada는 $[0, 3]$ 구간에 이 회의를 잡고 Tech Leads $#1$ 및 $#3$과 만날 수 있다. 이를 위해 회의 $4$을 취소해야 하며, 이것이 여기서의 최적해이다.