[Solution] Scheduling a Meeting Round F 2022 - Kick Start 2022 Solution

Problem

Scheduling meetings at Google is not an easy task. Even with the help of Google Calendar, Ada has a lot of difficulty with it!

Ada works as a Software Engineer at Google, and needs to get approval for her new project. In order to get an approval, she needs to meet with at least K$K$ of N$N$ Tech Leads.

Ada has access to the calendars of all N$N$ Tech Leads. For each Tech Lead, Ada can see all their scheduled meetings. The timeline in this problem can be viewed as D$D$ consecutive hours, and all meetings are in [0,D]$[0,\mathbf{D}]$ hours range, with both ends being integer numbers. Scheduled meetings, even for the same person, can overlap (people are notorious for this at Google!).

Ada needs to schedule an X$X$-hour-long meeting in the interval of [0,D]$[0,\mathbf{D}]$ hours, with both ends being integer numbers as well. At least K$K$ of N$N$ Tech Leads should be present for the whole meeting, that is their calendar should be completely free for the entire meeting duration.

Unfortunately, it might be the case that it is already impossible to find a slot to schedule such an X$X$-hour-long meeting. In that case, Ada will need to persuade some Tech Leads to cancel their existing meetings.

What is the minimum number of scheduled meetings that need to be canceled so that Ada can meet with at least K$K$ Tech Leads?

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.

The first line of each test case contains four integers N$N$, K$K$, X$X$, D$D$. N$N$ represents the number of Tech Leads, K$K$ is the minimum number of Tech Leads Ada needs to meet, X$X$ is the length of the meeting that needs to be set up, and D$D$ is the upper bound of the [0,D]$[0,\mathbf{D}]$ hour range representing the timeline of the problem — no meeting can end after D$D$.

The second line of each test case contains an integer M$M$, representing the number of scheduled meetings.

M$M$ lines follow. The i$i$-th of these contains three integer numbers Pi${\mathbf{P}}_{\mathbf{i}}$, Li${\mathbf{L}}_{\mathbf{i}}$, and Ri${\mathbf{R}}_{\mathbf{i}}$. These numbers represent that a Tech Lead Pi${\mathbf{P}}_{\mathbf{i}}$ has a scheduled meeting between the hours Li${\mathbf{L}}_{\mathbf{i}}$ and Ri${\mathbf{R}}_{\mathbf{i}}$, not including the endpoints (that is, the meeting can be seen as an (Li,Ri)$({\mathbf{L}}_{\mathbf{i}},{\mathbf{R}}_{\mathbf{i}})$ interval).

Note that all M$M$ meetings in the test case are independent, even if some of them have the same starting and ending time.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the minimum number of scheduled meetings that needs to be canceled so that Ada can schedule an X$X$-hour-long meeting with at least K$K$ Tech Leads.

Note on the Time Format

The timeline of this problem can be seen as an [0,D]$[0,\mathbf{D}]$ interval — that is, D$D$ consecutive hours, where D$D$ can be bigger than 24$24$.

A meeting in the interval (L,R)$(L,R)$ means the meeting starts at the beginning of the L$L$-th hour, and ends at the beginning of the R$R$-th hour, covering the whole time period in between, without any gaps (i.e. the interval is continuous). Endpoints are not included in an (L,R)$(L,R)$ interval. For Tech Leads attending Ada's scheduled meeting, Ada's new meeting can border some of their other non-canceled meetings — that is, it can start right when another meeting ends, or end right when another meeting starts, or both. A Tech Lead cannot attend Ada's meeting if they have any other non-canceled meetings overlapping with Ada's meeting at any point.

See explanation of the sample test cases for more clarity.

Limits

Time limit: 40 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤Pi≤N$1\le {\mathbf{P}}_{\mathbf{i}}\le \mathbf{N}$, for all i$i$.
0≤Li<Ri≤D$0\le {\mathbf{L}}_{\mathbf{i}}<{\mathbf{R}}_{\mathbf{i}}\le \mathbf{D}$, for all i$i$.

Test Set 1

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

Test Set 2

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

In Sample Case #1, Ada needs to schedule a two-hour-long meeting with at least two Tech Leads. She can schedule such a meeting between hours 1$1$ and 3$3$ with Tech Leads #1$\mathrm{\#}1$ and #3$\mathrm{\#}3$. In this case, no existing meetings need to be canceled.

In Sample Case #2, Ada needs to schedule a two-hour-long meeting with all three Tech Leads. She can schedule such a meeting in the interval [0,2]$[0,2]$, which will require meetings 2$2$ and 4$4$ to be canceled. Another option is to schedule a meeting in the interval [1,3]$[1,3]$. Both options require two meetings to be canceled, which is the minimum number possible.

In Sample Case #3, Ada needs to schedule a three-hour-long meeting with at least two Tech Leads. She can schedule this meeting in the interval [0,3]$[0,3]$, and meet with Tech Leads #1$\mathrm{\#}1$ and #3$\mathrm{\#}3$. This will require meeting 4$4$ to be canceled, and this is the optimal solution here.