Scheduling a Meeting

Scheduling meetings at Google is not an easy task. Even with Google Calendar, Ada has a hard time with it.

Ada is a Software Engineer at Google. To get approval for her new project, she must meet with at least $\mathbf{K}$ of the $\mathbf{N}$ Tech Leads.

Ada can see the calendars of all $\mathbf{N}$ Tech Leads, including every scheduled meeting. The timeline is $\mathbf{D}$ consecutive hours, and all meetings lie in the range $[0, \mathbf{D}]$ with integer endpoints. Scheduled meetings can overlap, even for the same person.

Ada needs to schedule a meeting of $\mathbf{X}$ hours within $[0, \mathbf{D}]$, with integer start and end times. At least $\mathbf{K}$ Tech Leads must be present for the whole meeting, which means their calendars must be completely free for its entire duration.

Sometimes no such slot exists. In that case, Ada must persuade some Tech Leads to cancel their existing meetings.

Find the minimum number of scheduled meetings that must be canceled so that Ada can meet with at least $\mathbf{K}$ Tech Leads.

The first line contains the number of test cases $\mathbf{T}$. Then $\mathbf{T}$ test cases follow.

The first line of each test case contains four integers $\mathbf{N}$, $\mathbf{K}$, $\mathbf{X}$, and $\mathbf{D}$. $\mathbf{N}$ is the number of Tech Leads, $\mathbf{K}$ is the minimum number of Tech Leads Ada needs to meet, $\mathbf{X}$ is the length of the meeting to schedule, and $\mathbf{D}$ is the upper bound of the range $[0, \mathbf{D}]$. No meeting can end after $\mathbf{D}$.

The second line contains an integer $\mathbf{M}$, the number of scheduled meetings.

Each of the next $\mathbf{M}$ lines contains three integers $\mathbf{P_i}$, $\mathbf{L_i}$, and $\mathbf{R_i}$. This means Tech Lead $\mathbf{P_i}$ has a scheduled meeting in the open interval $(\mathbf{L_i}, \mathbf{R_i})$, so the endpoints are not included. All $\mathbf{M}$ meetings are independent, even if some share the same start and end times.

For each test case, output one line in the form Case #x: y. Here $x$ is the test case number starting from 1, and $y$ is the minimum number of scheduled meetings that must be canceled so that Ada can schedule an $\mathbf{X}$-hour meeting with at least $\mathbf{K}$ Tech Leads.

The timeline can be seen as the interval $[0, \mathbf{D}]$, that is, $\mathbf{D}$ consecutive hours. $\mathbf{D}$ can be larger than 24.

A meeting $(L, R)$ starts at the beginning of hour $L$ and ends at the beginning of hour $R$, covering the whole time between them without gaps. The endpoints are not included. Ada's new meeting may border other non-canceled meetings of a Tech Lead: it can start right when another meeting ends, end right when another meeting starts, or both. A Tech Lead cannot attend Ada's meeting if any other non-canceled meeting overlaps with it at any point.