Social distansering

문제

I en skola går det $NN$ elever som varje dag ska äta lunch i skolmatsalen. Precis innan matsalen öppnar står alla elever på kö utanför. Det finns $KK$ köplatser totalt, numrerade från $00$ till $K-1K-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 $MM$ intervall av köplatser som måste vara tomma -- intervallet $l_i,r_{i}l\_i,r\_i$ indikerar att man inte får stå på någon av köplatserna $l_i,l_i+1,\mathrm{.}\mathrm{.}\mathrm{.}{r}_{i}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 $DD$, och sedan säga att varje elev måste minst hålla ett avstånd $DD$ från närmsta andra elev. En elev på köplats $ii$ och en elev på köplats $jj$ har avstånd $\mathrm{\mid }i-j\mathrm{\mid }|i-j|$.

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

입력

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

출력

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