Lõikude tükeldamine

문제

Arvteljel on antud $NN$ positiivsete täisarvuliste koordinaatidega lõiku $[L_1,R_1][L\_1,\; R\_1]$, \ldots, $[L_N,R_N][L\_N,\; R\_N]$. Üks tükeldamis\-operatsioon asendab lõigu $[L,R][L,\; R]$ lõikudega $[L,M][L,\; M]$ ja $[M,R][M,\; R]$, kus $MM$ on positiivne täis\-arv ja . Tükeldada võib nii alguses antud kui ka eelmiste tükeldamistega saadud lõike.

Ülteme, et lõik $[A,B][A,\; B]$, kus on positiivsed täisarvud, kattub tugevalt lõiguga $[L,R][L,\; R]$, kui lõik $[A,B][A,\; B]$ katab vähemalt poole lõigu $[L,R][L,\; R]$ pikkusest.

Ülesanne on leida vähim võimalik lõigu $[A,B][A,\; B]$ pikkus, mille korral on võimalik sisendis antud $NN$ lõigule rakendada $KK$ tükeldamisoperatsiooni nii, et lõik $[A,B][A,\; B]$ kattub tugevalt kõigi $N+KN\; +\; K$ saadud lõiguga.

입력

Esimesel real on täisarvud $NN$ ja $KK$ ($1\le N\le {10}^{5}1\; \backslash le\; N\; \backslash le\; 10^5$, $0\le K\le {10}^{14}0\; \backslash le\; K\; \backslash le\; 10^\{14\}$).

Järgmised $NN$ rida kirjeldavad lõike. Nende hulgas $ii$. real on $i\mathrm{.}i.$ lõigu vasaku ja parema otspunkti täisarvulised koordinaadid $L_{i}L\_i$ ja $R_{i}R\_i$ (). Võib eeldada, et neile lõikudele on võimalik $KK$ tükeldamisoperatsiooni rakendada. Mõned antud lõikudest võivad üksteisega täpselt kokku langeda.

출력

Väljastada üks täisarv: eelpool kirjeldatud tugevalt kattuva lõigu $[A,B][A,\; B]$ vähim võimalik pikkus.