P15466 [ICPC 2024 WF] Citizenship 公民身份

4s 2048MB 翻译来源：loj #6973. [「ICPC World Finals 2024」公民身份](https://loj.ac/p/6973)。

自从你搬到另一个国家已经过去了很长一段时间，现在你决定是时候申请成为该国的公民了。这个新国家对所有申请者有严格的居住要求。要提交申请，你必须在过去连续 $y$ 年中，每年至少在该国停留 $d$ 天。这些年份是按申请日期向前推算的 $12$ 个月周期来计算的。 在本题中，假设一个日历年有 $12$ 个月，共 $365$ 天，每个月的具体天数如下表所示： | 月份 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | |:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:| | 天数 | 31 | 28 | 31 | 30 | 31 | 30 | 31 | 31 | 30 | 31 | 30 | 31 | 例如，如果你计划在 2024-09-19 申请公民身份，你必须在 2023-09-19 到 2024-09-18、2022-09-19 到 2023-09-18 等连续 $y$ 个 $12$ 个月周期内，每周期至少在该国停留 $d$ 天。 你已经在该国居住了至少 $y$ 年，但由于经常旅行，你不确定自己是否符合居住要求。请编写一个程序，根据你的旅行记录，找出你最早可以提交公民身份申请的日期。

第一行包含三个整数 $n$、$y$ 和 $d$ $(1 \leq n \leq 500, 1 \leq y \leq 1\,000, 1 \leq d \leq 365)$。其中，$n$ 表示你离开该国的次数，$y$ 和 $d$ 分别表示该国居住要求的年数和每年所需的最少停留天数，如上所述。 接下来的 $n$ 行，每行包含两个日期，格式为 $\texttt{YYYY-MM-DD}$ $(0000 \leq \texttt{YYYY} \leq 5000, 01 \leq \texttt{MM} \leq 12, 01 \leq \texttt{DD} \leq 31)$。这两个日期之间（包括首尾日期）你在国外。输入中的所有日期按升序排列，唯一可能相等的日期是同一行的两个日期。所有给定的日期都是有效的。

输出你满足居住要求的最早日期。该日期必须晚于输入中的最后一个日期。