CF1379D New Passenger Trams

每天都有许多货运列车从 Kirnes 星球出发。该星球的一天包含 $h$ 小时，每小时包含 $m$ 分钟，其中 $m$ 是一个偶数。现在有 $n$ 辆货运列车，它们每天都在相同的时间发车：第 $i$ 辆列车在 $h_i$ 小时 $m_i$ 分钟发车。 政府决定增设客运有轨电车：他们计划以半小时为间隔增设定期电车服务。这意味着当天的第一班电车必须在 $0$ 小时 $t$ 分钟发车，其中 $0 \le t < \frac{m}{2}$，第二班电车在第一班发车后 $\frac{m}{2}$ 分钟发车，依此类推。这样的时刻表保证每小时恰好有两班客运电车，这是一项很大的改进。 为了让乘客安全上车，电车必须提前 $k$ 分钟到达。在乘客上车期间，任何货运列车都不能发车。然而，货运列车允许在上车开始的那一刻以及客运电车发车的那一刻发车。注意，如果第一班客运电车在 $0$ 小时 $t$ 分钟发车，且 $t < k$，那么货运列车在当天最后 $k-t$ 分钟内也不能发车。  上图为客运电车运行的正确方式示意图。此处 $h=2$（因此客运电车数量为 $2h=4$），货运列车数量为 $n=6$。客运电车用红色标记（注意它们之间的间隔相同）。货运列车用蓝色标记。每班客运电车前的长度为 $k$ 的时间段用红色高亮。注意这些时间段内没有货运列车。不幸的是，可能无法在不取消部分货运列车的情况下满足政府的要求。请帮助政府找到最优的 $t$ 值，使得在所有客运电车按计划发车的情况下，需要取消的货运列车数量最少。

输入的第一行包含四个整数 $n$、$h$、$m$、$k$（$1 \le n \le 100\,000$，$1 \le h \le 10^9$，$2 \le m \le 10^9$，$m$ 为偶数，$1 \le k \le \frac{m}{2}$）——每天的货运列车数量、星球的一天的小时数和分钟数，以及每班客运电车的上车时间。 接下来 $n$ 行，每行包含两个整数 $h_i$ 和 $m_i$（$0 \le h_i < h$，$0 \le m_i < m$）——第 $i$ 辆货运列车的发车时间。保证没有两辆货运列车在同一时刻发车。

输出的第一行应包含两个整数：需要取消的最少货运列车数量，以及最优的客运电车首班发车时间 $t$。第二行输出需要取消的货运列车编号。

在第一个样例中，第一班电车可以在 0 小时 0 分钟发车。此时，16 小时 0 分钟的货运列车可以与客运电车同时发车，17 小时 15 分钟的货运列车可以在即将到来的客运电车开始上车的那一刻发车。 在第二个样例中，无法设计出不取消任何货运列车的客运电车时刻表：如果 $t \in [1, 15]$，则 16 小时 0 分钟的货运列车无法发车（因为上车时间为 16 分钟）。如果 $t = 0$ 或 $t \in [16, 29]$，则 17 小时 15 分钟的货运列车无法发车。然而，如果取消第二辆货运列车，可以选择 $t = 0$。另一种选择是取消第一辆列车并选择 $t = 13$。 由 ChatGPT 4.1 翻译