题目描述

自从你搬到另一个国家已经过去了很长一段时间，现在你决定是时候申请成为该国的公民了。这个新国家对所有申请者有严格的居住要求。要提交申请，你必须在过去连续 $y$ 年中，每年至少在该国停留 $d$ 天。这些年份是按申请日期向前推算的 $12$ 个月周期来计算的。

在本题中，假设一个日历年有 $12$ 个月，共 $365$ 天，每个月的具体天数如下表所示：

例如，如果你计划在 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)$。这两个日期之间（包括首尾日期）你在国外。输入中的所有日期按升序排列，唯一可能相等的日期是同一行的两个日期。所有给定的日期都是有效的。

输出格式

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

3 5 240
2022-02-28 2022-10-01
2022-11-11 2022-11-11
2023-12-30 2024-01-01

2024-05-31

3 5 240
2011-11-11 2012-12-12
2022-02-28 2022-10-01
2025-01-01 2025-06-30

2028-02-26