题目描述

小红想要购买木材。现在商家有一根原木，长度为 $n$ ，但这块原木上只有一些结实的部分适合做木材。商家告诉小红可以从这根原木上选取长度为 $k$ 的一段购买并截取。小红希望他购买的木材能够包含尽可能多的结实部分，请你指出小红购买后能够获得木材的总长度最长是多少。

输入描述

第一行输入两个正整数 $n,m,k$，代表原木初始长度，结实部分的数量,以及小红能够购买的原木的长度。小红只能购买整数长度区间部分的原木。

接下来的 $m$ 行，每行输入两个正整数 $l_i$ , $r_i$，代表原木第 $i$ 块结实部分的起止区间。

1 $\leqslant$ k < n $\leqslant$1000000000

1 < m < 100000

0 < $l_i$ < $r_i$< n

保证任意两个区间是不重叠的。

输出描述

一个正整数，代表能够获得的木材最长长度

样例

输入

5 2 3
1 2
3 5

输出

2

提示

区间(1,2)代表从 1 到 2 这个长度单位的原木是结实部分，可以做木材，区间(3,5)代表从 3 到 5 这个长度单位的原木是结实部分，可以做木材。小红只能购买整数长度区间部分的原木，所以这个样例可以选择购买区间 (2, 5) 的原木，最终收获长度为2的木材。