P13455 [GCJ 2008 Qualification] Train Timetable

一条铁路线有两个车站，A 和 B。列车可以在一天内多次往返于 A 和 B 之间。当一列列车从 A 到达 B（或从 B 到达 A）后，需要一定的时间才能准备好进行返程——这段时间称为周转时间。例如，如果一列列车在 12:00 到达，且周转时间为 0 分钟，则它可以在 12:00 立即出发。 列车时刻表给出了所有 A 到 B 和 B 到 A 之间的行程的出发和到达时间。铁路公司需要知道，为了使时刻表能够顺利运行，早上分别需要在 A 和 B 各准备多少列列车：每当有列车需要从 A 或 B 出发时，必须有一列已经准备好的列车在该站等候。铁路线中有会车段，因此列车的到达顺序不一定与出发顺序相同。列车不能执行时刻表上未列出的行程。

输入的第一行为测试用例数 $N$。接下来有 $N$ 组测试数据。 每组测试数据包含若干行。第一行为周转时间 $T$，单位为分钟。下一行为两个整数 $N_A$ 和 $N_B$，分别表示从 A 到 B 和从 B 到 A 的行程数。接下来有 $N_A$ 行，每行包含两个字段，分别为该行程的出发时间和到达时间，格式为 HH:MM。每个行程的出发时间早于到达时间，所有出发和到达均在同一天内。行程的顺序不一定按时间排序。小时和分钟均为两位数，前导零补齐，采用 24 小时制（00:00 到 23:59）。 在这 $N_A$ 行之后，有 $N_B$ 行，给出从 B 到 A 的行程的出发和到达时间。

对于每组测试数据，输出一行，格式为 "Case #$x$: "，后接需要在 A 和 B 各自准备的列车数量。

**数据范围** **小数据集（5 分，测试点 1 - 可见）** - $1 \leq N \leq 20$ - $0 \leq N_A, N_B \leq 20$ - $0 \leq T \leq 5$ **大数据集（20 分，测试点 2 - 隐藏）** - $1 \leq N \leq 100$ - $0 \leq N_A, N_B \leq 100$ - $0 \leq T \leq 60$ 由 ChatGPT 4.1 翻译