| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1 | 0 | 0 | 0.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.
3 3 1 7 3 8 2 9
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.
6 15 4 10 2 8 7 14 1 9 5 12 3 13
7