Se consideră N intervale [Ai,Bi], 1 ≤ i ≤ N disjuncte.

Tuturor intervalelor li se aplică o operație de extindere la ambele capete cu o valoare naturală x, astfel încât după extindere cu valoarea x, intervalul [Ai,Bi] va deveni intervalul [Ai-x,Bi+x], 1 ≤ i ≤ N.

După extindere, spunem că intervalele [Ai,Bi] și [Aj,Bj] aparțin aceluiași grup de intervale dacă ele se intersectează sau dacă există un interval [Ak,Bk] astfel încât [Ai,Bi] se intersectează cu [Ak,Bk] iar intervalele [Ak,Bk], [Aj,Bj] aparțin aceluiași grup de intervale.

Cerința

Să se determine valoarea minimă x cu care vor trebui să fie extinse toate intervalele astfel încât să se formeze un grup cu cel puțin P intervale.

Date de intrare

Fișierul de intrare intervale3.in conține pe prima linie numerele naturale N și P cu semnificația din enunț. Pe următoarele N linii sunt descrise cele N intervale, câte un interval pe linie. Pentru fiecare interval i sunt specificate capetele sale Ai şi Bi.

Date de ieșire

Fișierul de ieșire intervale3.out va conţine pe prima linie numărul natural x ce reprezintă valoarea minimă cu care vor trebui extinse intervalele astfel încât să se obțină cel puțin un grup format din cel minimum P intervale.

Restricții și precizări

• 2 ≤ N ≤ 100 000
• -1 400 000 000 ≤ Ai < Bi ≤ 1 400 000 000
• 2 ≤ P ≤ N
• Două intervale se intersectează dacă au cel puţin un punct comun
• Pentru 30% dintre teste N ≤ 10 000

Exemplu:

intervale3.in

7 3
8 9
21 25
14 17
1 4
28 32
35 42
100 200

intervale3.out

2

Explicație

După extinderea cu 2 a celor 7 intervale se obțin intervalele:
[6,11]
[19,27]
[12,19]
[-1,6]
[26,34]
[33,44]
[98,202]

Se formează astfel 3 grupuri de intervale:

• Grupul 1: [-1,6], [6,11]
• Grupul 2: [12,19], [19,27], [26,34], [33,44]
• Grupul 3: [98,202]

Grupul 2 este format din cel puțin 3 intervale.