사회적 거리 두기

한 학교에 매일 급식실에서 점심을 먹어야 하는 $N$명의 학생이 있다. 급식실이 문을 열기 직전에 모든 학생이 밖에 줄을 선다. 줄을 설 수 있는 자리는 모두 $K$개이고, $0$번부터 $K-1$번까지 번호가 붙어 있다. 각 자리에는 최대 한 명이 설 수 있다. 화재 위험 때문에 비어 있어야 하는 자리도 있다. 구체적으로, 비어 있어야 하는 자리 구간이 $M$개 있다. 구간 $l_i,r_i$는 $l_i, l_i+1, \ldots, r_i$번 자리 어디에도 서면 안 된다는 뜻이다. 어떤 두 구간도 겹치지 않는다.

학교 교장은 얼마 전 어떤 "팬데믹"에 대해 듣고는 과감한 조치를 취할 때라고 판단한다. 교장은 급식실 줄에 사회적 거리 두기를 도입하려 한다. 정수 $D$를 하나 정하고, 각 학생이 가장 가까운 다른 학생과 적어도 $D$만큼 떨어져 있어야 한다고 말할 것이다. 자리 $i$에 있는 학생과 자리 $j$에 있는 학생 사이의 거리는 $|i-j|$이다.

모든 학생이 여전히 동시에 급식실 줄에 설 수 있게 하는 가장 큰 $D$를 교장이 찾도록 도와주자!

첫째 줄에 세 정수 $N$, $M$, $K$가 주어진다 ($2 \leq N \leq 10^9$, $0 \leq M \leq 10^6$, $N \leq K \leq 10^{12}$). 각각 학생 수, 금지 구간의 수, 자리 수이다. 이어서 $M$개의 줄에 정수 $2$개 $l_i$, $r_i$가 주어진다 ($0 \le l_i \le r_i \le K-1$). $i$번 구간의 시작과 끝이다. 어떤 두 구간도 겹치지 않고, 금지되지 않은 자리가 적어도 $N$개 있음이 보장된다.

정수 하나를 출력한다. 가능한 가장 큰 사회적 거리 두기 값이다.