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

Pentru ca a fost batut de prea multe ori la 'Jocul pe grid' de catre Presedinte, Primul Ministru planuieste o lovitura de stat. Din fericire, Dubluveu, a fost informat la timp de intentiile Sefului Guvernului si are de gand sa-si organizeze o aparare temeinica. Palatul Prezidential este plasat strategic, neputandu-se ajunge la acesta decat pe o singura sosea de lungime $L$ kilometri. Pe marginea sa Dubluveu cere amplasarea, in $N$ locatii fixe, a doua tipuri de dispozitive: lansatoare de rachete "sol-sol":http://en.wikipedia.org/wiki/Surface-to-surface_missile si lansatoare de rachete "sol-aer":http://en.wikipedia.org/wiki/Surface-to-air_missile (cate un tip in fiecare locatie). Daca un dispozitiv (nu conteaza de ce tip) este plasat in locatia $i$, acesta va putea distruge orice forma de viata doar intr-un interval $[a{~i~},b{~i~}]$. Pentru a fi sigur ca Primul Ministru nu v-a putea ajunge la el, Dubluveu vrea ca fiecare punct al soselei sa fie pazit de +ambele+ tipuri de dispozitive.

Pentru ca a fost batut de prea multe ori la 'Jocul pe grid' de catre Presedinte, Primul Ministru planuieste o lovitura de stat. Din fericire, Dubluveu, a fost informat la timp de intentiile Sefului Guvernului si are de gand sa-si organizeze o aparare temeinica. Palatul Prezidential este plasat strategic, neputandu-se ajunge la acesta decat pe o singura sosea de lungime $L$ kilometri. Pe marginea sa Dubluveu cere amplasarea, in $N$ locatii fixe, a doua tipuri de dispozitive: lansatoare de rachete "sol-sol":http://en.wikipedia.org/wiki/Surface-to-surface_missile si lansatoare de rachete "sol-aer":http://en.wikipedia.org/wiki/Surface-to-air_missile (cate un tip in fiecare locatie). Daca un dispozitiv (nu conteaza de ce tip) este plasat in locatia $i$, acesta va putea distruge orice forma de viata doar intr-un interval $[a{~i~},b{~i~}]$. Pentru a fi sigur ca Primul Ministru nu va putea ajunge la el, Dubluveu vrea ca fiecare punct al soselei sa fie pazit de +ambele+ tipuri de dispozitive.

h2. Cerinta

h2. Date de intrare

Pe prima linie a fisierului de intrare $sn.in$ se afla doua numere $L$ si $N$. Pe urmatoarele $N$ linii se afla doua numere $a{~i~}$, $b{~i~}$, cu seminifcatia ca un dispozitiv plasat in locatia $i$ va putea distruge orice forma de viata ce se afla in intervalul $[a{~i~},b{~i~}]$.

Pe prima linie a fisierului de intrare $sn.in$ se afla doua numere $L$ si $N$. Pe urmatoarele $N$ linii se afla doua numere $a{~i~}$, $b{~i~}$, cu semnificatia ca un dispozitiv plasat in locatia $i$ va putea distruge orice forma de viata ce se afla in intervalul $[a{~i~},b{~i~}]$.

h2. Date de iesire