Planificare

planificare

== include(page="template/taskheader" task_id="planificare") ==

$Talent Day$ se apropie la trustul TV $Blomkvist$, iar presedintele Mike are nevoie de voi pentru a realiza grila de programe. $N$ participanti s-au inscris pentru a isi expune talentele, fiecare comunicand intervalul de timp de care are nevoie. Lantul TV al lui Mike este format din $K$ posturi, ({$Blomkvist 1, Blomkvist 2, ... Blomkvist K$}) care transmit independent unul de altul. Din cauza ca toate cele $K$ posturi sunt la fel de populare, participantilor le este indiferent la care vor aparea. Stiind ca la orice moment orice post va transmite un singur show, determinati care este numarul maxim de show-uri care pot fi televizate.
 

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $planificare.in$ va contine pe prima linie $2$ numere naturale, $N$ si $K$. Pe fiecare din urmatoarele $N$ linii se vor afla cate $2$ valori, $start{~i~}$ si $stop{~i~}$, reprezentand intervalul de timp in care participantul $i$ isi poate desfasura activitatea.

Fişierul de intrare $planificare.in$ ...

h2. Date de ieşire

Fişierul de ieşire $planificare.out$ va contine pe prima linie numarul cerut de Mike.

În fişierul de ieşire $planificare.out$ ...

h2. Restricţii si precizari

h2. Restricţii

* $1 ≤ N ≤  100.000$
* $1 ≤ K ≤  100.000$
* $1 ≤ start{~i~} ≤ stop{~i~} ≤  1.000.000.000$
* $Pentru 30% din teste, N ≤ 2000, iar pentru alte 10% din teste, K = 1$
* $La fiecare televiziune un show poate sa inceapa chiar in acelasi moment in care s-a terminat precedentul.$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. planificare.in |_. planificare.out |

| 2 1
1 4
4 8
| 2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="planificare") ==

6932