Simulation - Lot 2013 Baraj 2 Juniori | intervale

Se consideră $N$ intervale $[A_i, B_i] \ (1 \leq i \leq 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 $[A_i, B_i]$ va deveni intervalul $[A_i-x, B_i+x]$, $(1 \leq i \leq N)$.

După extindere, spunem că intervalele $[A_i, B_i]$ și $[A_j, B_j]$ aparțin aceluiași grup de intervale dacă ele se intersectează sau dacă există un interval $[A_k, B_k]$ astfel încât $[A_i,B_i]$ se intersectează cu $[A_k, B_k]$ iar intervalele $[A_k, B_k]$, $[A_j, B_j]$ aparțin aceluiași grup de intervale.

Cerinţă

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 intervale.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 $A_i$ şi $B_i$.

Date de ieșire

Fişierul de ieșire intervale.out 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 \leq N \leq 100 \ 000$
• $-1 \ 400 \ 000 \ 000 \leq A_i < B_i \leq 1 \ 400 \ 000 \ 000$
• $2 \leq P \leq N$
• Două intervale se intersectează dacă au cel puţin un punct comun
• Pentru $30\%$ dintre teste $N \leq 10 \ 000$

Exemplu

intervale.in

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

intervale.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