P13916 [PO Final 2024] 瓦萨滑雪节 / Vasaloppet

查洛特正在电视上看瓦萨滑雪节。节目从第 $0$ 秒开始，到第 $T$ 秒结束。不幸的是，节目中还有 $N$ 段广告，持续 $N$ 个不重叠的秒级时间段，介于第 $0$ 秒和第 $T$ 秒之间。查洛特看到起跑线上的选手们后深受启发，想在比赛期间自己也去滑雪。滑雪之旅需要 $S$ 秒，她必须在第 $T$ 秒前回来（以便看到谁是赢家）。 查洛特希望选择一个时间去滑雪，以便尽可能少地错过瓦萨滑雪节。你的任务是计算查洛特在最佳选择滑雪时间的情况下，最少会错过多少秒的瓦萨滑雪节。错过的秒数是指查洛特外出滑雪期间，没有广告播放的秒数。  上图描述了样例 $1$。红色矩形表示广告时段。如果查洛特在第一个广告时段开始时出发滑雪，并在第二个广告时段结束时回家，她将只错过 $2$ 秒的瓦萨滑雪节。

输入的第一行包含三个整数 $N, T,S$ ($0 \leq N \leq 10^5$, $1 \leq S \leq T \leq 10^9$)。$N$ 是广告时段的数量，$T$ 是节目持续的秒数，$S$ 是滑雪之旅的持续秒数。 接下来 $N$ 行，每行包含两个整数 $l_ i, r_ i$ ($0 \leq l_ i < r_ i \leq T$)，表示第 $i$ 个广告时段从第 $l_ i$ 秒持续到第 $r_ i$ 秒。 广告时段按其出现顺序给出，并且所有时段互不重叠且已排序，这意味着对于 $i < N$，有 $r_ i < l_{i+1}$。

输出一个整数，表示查洛特在最佳选择滑雪时间的情况下，滑雪期间最少会错过多少秒的瓦萨滑雪节。请注意，滑雪之旅可以恰好在第 $T$ 秒结束。例如，如果 $S=3$ 且 $T=3$，滑雪之旅可以覆盖瓦萨滑雪节的整个持续时间。

### 子任务 **本题采用捆绑测试。** | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $10$ | $N=1$ | | $2$ | $25$ | $N \leq 1000$ | | $3$ | $30$ | $T \leq 10^6$ | | $4$ | $35$ | 无额外限制 |