题目描述

有 $m$ 个花盆排成一列，每个花盆可以种至多一朵花。给定 $n$ 个操作，每个操作包含两个整数 $l_i,r_i$，表示将 $[l_i,r_i]$ 中的花盆种上花。保证不存在一个花盆使得有两个不同的操作在其中种花。保证 $\forall i\in [1,n-1],l_i< l_{i+1}$。

你可以再种至多 $k$ 朵花，让美观值最大：美观值定义为一个最大的整数 $len$，满足存在一个长度为 $len$ 的区间使得区间中的每个位置都种有花。

输入格式

第一行三个整数 $m,n,k$。

接下来 $n$ 行，每行两个整数 $l_i,r_i$。

输出格式

一个整数，表示最大的美观值。

样例一

input

10 2 3
2 3
7 9

output

8

样例二

input

20 3 10
1 2
9 12
20 20

output

16

限制与约定

对于所有数据，满足 $1\le m\le 10^{18}$，$1\le n\le 10^6$，$0\le k\le 10^{18}$，$1\le l_i\le r_i\le m$。

由于读入量较大，请选手使用较快速的读入方式。