시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB1000.000%

문제

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

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

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

입력

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

Järgmised $N$ rida kirjeldavad lõike. Nende hulgas $i$. real on $i.$ lõigu vasaku ja parema otspunkti täisarvulised koordinaadid $L_i$ ja $R_i$ ($1 \le L_i < R_i \le 10^9$). Võib eeldada, et neile lõikudele on võimalik $K$ 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]$ vähim võimalik pikkus.

예제 입력 1

3 3
1 7
3 8
2 9

예제 출력 1

4

Lõigu $[3, 8]$ võime tükeldada kolmeks: $[3, 5]$, $[5, 7]$ ja $[7, 8]$; lõigu $[2, 9]$ võime tükeldada kaheks: $[2, 6]$ ja $[6, 9]$; lõigu $[1, 7]$ võime jätta muutmata. Siis katab lõik $[4, 8]$ pikkusega $4$ vähemalt poole igast saadud $6$ lõigust. On võimalik kontrollida, et ei leidu ühtki lühemat lõiku, mis kõiki tingimusi rahuldaks.

예제 입력 2

6 15
4 10
2 8
7 14
1 9
5 12
3 13

예제 출력 2

7