Charlotte 正在电视上观看 Vasaloppet（瓦萨滑雪节）。广播从第 $0$ 秒开始，到第 $T$ 秒结束。不幸的是，期间还有 $N$ 个广告时间，对应第 $0$ 秒到第 $T$ 秒之间 $N$ 个互不重叠的时间段。Charlotte 看到起跑线上的选手们深受启发，也想在比赛期间自己去滑雪。滑雪需要花费 $S$ 秒，且她必须不晚于第 $T$ 秒返回（以便观看谁获得了冠军）。

Charlotte 希望选择一个滑雪的时间段，使得她错过的 Vasaloppet 比赛内容尽可能少。你的任务是计算如果 Charlotte 最优地选择滑雪时间，她最少会错过多少秒的 Vasaloppet 比赛。错过的秒数是指 Charlotte 出去滑雪且当时没有播放广告的秒数。

图 1：该图描述了第一个样例。红色矩形表示广告时间。如果 Charlotte 在第一个广告开始时开始滑雪，并在第二个广告结束时返回，她将只错过 2 秒的 Vasaloppet 比赛。

输入格式

输入的第一行包含三个整数 $N, T$ 和 $S$（$0 \le N \le 10^5$，$1 \le S \le T \le 10^9$）。其中 $N$ 是广告时间的个数，$T$ 是广播的总时长（秒），$S$ 是滑雪的持续时间（秒）。

接下来的 $N$ 行，每行包含两个整数 $l_i, r_i$（$0 \le l_i < r_i \le T$），表示第 $i$ 个广告时间从第 $l_i$ 秒持续到第 $r_i$ 秒。

广告时间按发生顺序给出，且所有广告时间均互不相交并已排序，这意味着对于 $i < N$，有 $r_i < l_{i+1}$。

输出格式

输出一个整数，表示如果最优地选择滑雪时间，Charlotte 在滑雪期间最少错过的 Vasaloppet 比赛秒数。注意，滑雪可以正好在第 $T$ 秒结束。例如，如果 $S = 3$ 且 $T = 3$，滑雪可以覆盖 Vasaloppet 的整个时长。

子任务

您的解法将在多个测试点结合（子任务）上进行测试。要获得某个子任务的分数，必须通过该子任务中的所有测试用例。

样例

输入样例 1

2 10 5
1 2
4 6

输出样例 1

2

输入样例 2

4 10 7
0 2
3 4
5 6
9 10

输出样例 2

3

输入样例 3

0 1000000000 1000000000

输出样例 3

1000000000