6. Mandarínske kráľovské problémy

V Mandarínsku žije samoľúby král Nenásytnan Veľký, ktorý má rád mandarínky. Má ich až tak rád, že každý deň počas mandarínkovej sezóny jednu zje¹. A keďže on je veľmi nenástytný tak každý deň musí zjesť tú najväčšiu čo sa v predchádzajúci deň v Mandarínsku urodila. V Mandarínsku počas sezóny narastie každý deň \(n\) mandariniek. Tieto mandarínky sa potom rovnomerne poukladajú na jednu dlhú linku, kde ich manuálne zoraďujú pracovníci od najmenšej po najväčšiu s cieľom aby sa najväčšia mandarínka dostala priamo na kráľovský stôl. Každý pracovník je zamestnaný na určitom úseku linky a jeho úlhou je usporiadať mandarínky na linke podľa veľkosti v rámci jeho úseku (rozsahu rúk).

Keďže aj do Mandarínska prišla pandémia, z hygienických dôvodov sa môže na každom pracovisku nachádzať naraz iba jeden zamestnanec. Podľa nariadenia hlavného hygienika Mandarínska sú zamestnanci každý deň púšťaní do práce postupne podľa ich zamestnaneckého čísla. Každý z nich tam môže byť iba nevyhnutný čas a potom musí ísť domov.

Tento postup musí dodržiavať aj mandarínková triediaca linka. Šéf tejto linky Kleofáš Múdry rozmýšla ako ho najlepšie implementovať. Počas prvých dní pandémie do firmy púšťal všetkých zamestnancov postupne, tak ako to vyžaduje nariadenie. Potom si však uvedomil, že keďže jedinou úlohou celej linky je nájsť najväčšiu mandarínku a poslať ju ku kráľovi, možno by mohol ako dobrý šéf nechať niektorých svojich zamestnancov doma. Teraz rozmýšla nad tým koľko zamestnancov reálne musí chodiť do práce aby linka plnila to na čo bola určená. Viete mu s tým pomôcť?

Úloha

Na triediacej linke sa v pravidelných rozostupoch nachádza \(n\) mandaríniek. Vo firme pracuje \(m\) zamestnancov. Každý z nich príde do práce a podľa veľkosti vzostupne utriedi mandarínky na linke medzi \(a_i\)-tou a \(b_i\)-tou vrátane, pričom na linke udržiava pravidelné rozostupy. Kleofáš chce vybrať čo najmenej zamestnancov tak, aby vedel zaručiť že ak by prišli do práce iba oni, tak nech je najväčšia mandarínka na začiatku dňa na linke na ľubovolnom mieste, na konci dňa vždy skončí na pozícii \(n\). Zistite koľko najmenej zamestnancov musí vybrať do smeny. Nezabudnite že do práce musia prísť v poradí podľa zamestnaneckého čísla.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú dve celé čísla \(n,m\) (\(1 \leq n,m \leq 300\,000\)) – denná produkcia Mandarínska a počet zamestnancov na linke. Na ďaľších \(m\) riadkoch sa nachádzajú intervaly na ktorých pracujú jednotliví zamestnanci. Na \(i\)-tom riadku sa nachádzajú čísla \(a_i\) a \(b_i\) (\(1\leq a_i \leq b_i \leq n\)), kde \([a_i, b_i]\) je interval ktorý je triedený zamestnancom so zamestnaneckým číslom \(i\).

Formát výstupu

Na výstup vypíšte jediné číslo – minimálny počet zamestnancov, ktorý musia prísť do práce na to, aby sa najväčšia mandarínka zaručene dostala na poslednú pozíciu na triediacej linke. V prípade že je na triediacej linke už teraz taký zmätok, že aj bez vynechania zamestnanca sa najväčšia mandarínka nie nutne dostane ku kráľovi, vypíšte \(-1\).

Hodnotenie

Sú \(4\) sady vstupov. V jednotlivých sadách platia nasledovné obmedzenia:

1. \(n \leq 10\), \(m \leq 10\)
2. \(n \leq 100\), \(m \leq 100\)
3. \(n \leq 300\,000\), \(m \leq 2\,000\)
4. \(n \leq 300\,000\), \(m \leq 300\,000\)

Príklady

Input:

6 2
1 4
4 6

Output:

2

Obaja zamestnanci musia prísť do práce, inak by sa najväčšia mandarínka z pozície 3 nemohla dostať na koniec linky na pozíciu 6.

Input:

6 2
4 6
1 4

Output:

-1

V tomto prípade ak sa najväčšia mandarínka nachádza na pozícii 3 tak keď príde do práce prvý zamestnanec tak ju neposunie a druhý zamestnanec ju posunie iba na pozíciu č. 4. Aj keď prídu do práce všetci zamestnanci, najväčšia mandarínka na konci dňa nemusí byť na poslednej pozícii.

Input:

6 3
1 4
2 5
3 6

Output:

2

Stačí ak do práce príde iba prvý a tretí zamestnanec. Ak najväčšia mandarínka začínala medzi pozíciami 1 až 4, prvý zamestnanec ju umiestni na pozíciu 4. Tretí zamestnanec ju stadiaľ vie položiť na koniec, a zvláda aj prípad kedy mandarínka bola na začiatku na pozícií 5.