Problem G
Social distansering

I en skola går det $N$ elever som varje dag ska äta lunch i skolmatsalen. Precis innan matsalen öppnar står alla elever på kö utanför. Det finns $K$ köplatser totalt, numrerade från $0$ till $K-1$. På varje köplats kan maximalt en person stå. Vissa köplatser måste på grund av brandrisk vara tomma. Närmare bestämt finns det $M$ intervall av köplatser som måste vara tomma – intervallet $l_ i,r_ i$ indikerar att man inte får stå på någon av köplatserna $l_ i,l_ i+1,...r_ i$. Det garanteras att inget intervall överlappar med något annat.

Skolans rektor har just fått höra om nån slags "pandemi", och bestämmer att det är dags för drastiska åtgärder. Rektorn vill införa social distansering i lunchkön. Han tänker välja ett heltal $D$, och sedan säga att varje elev måste minst hålla ett avstånd $D$ från närmsta andra elev. En elev på köplats $i$ och en elev på köplats $j$ har avstånd $|i-j|$.

Hjälp rektorn hitta det största $D$ han kan välja så att alla elever fortfarande kan stå i lunchkön samtidigt!

Indata

Den första raden innehåller tre heltal $N$, $M$ och $K$ ($2 \leq N \leq 10^9$, $0 \leq M \leq 10^5$ och $N \leq K \leq 10^{12}$) – antal elever, antal förbjudna intervall och antal köplatser. Därefter följer $M$ rader med $2$ heltal på varje, $l_ i$, $r_ i$ ($0 \le l_ i \le r_ i \le K-1$) start och slut för intervall nummer $i$. Det garanteras att inget par av dessa intervall överlappar, och att det finns minst $N$ köplatser som inte är förbjudna.

Utdata

Skriv ut ett heltal – den största möjliga sociala distanseringen.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

3 2 10
3 5
7 8

3

4 4 30
0 8
20 24
27 29
9 9

4

9 0 99999999999

12499999999