题目描述

查洛特正在电视上看瓦萨滑雪节。节目从第 $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$，滑雪之旅可以覆盖瓦萨滑雪节的整个持续时间。

2 10 5
1 2
4 6

2

4 10 7
0 2
3 4
5 6
9 10

3

0 1000000000 1000000000

1000000000

提示

子任务

本题采用捆绑测试。