AlgoLiga 2018

1 września to dla wielu powrót do szkoły oraz powrót do nauki przedmiotów zarówno tych lubianych, jak i nie. Bajteusz nigdy nie lubił chemii. Dzisiajsza lekcja jednak bardzo go zaciekawiła. Nauczyciel kazał uczniom przeprowadzić eksperyment pokazujący działanie różnych rodzajów kwasów. Polegał on na upuszczaniu w ściśle określonych momentach kropli stężonego kwasu na długi metalowy pręt. Celem ćwiczenia było zmierzenie czasu jaki jest potrzebny aby cały pręt pokrył się rdzą. Bajteusz szybko zauważył, że ognisko rdzy na pręcie zainicjowane przez spadającą kroplę rozszerza się w tempie 1mm/sek w obydwu kierunkach aż do końca pręta. Postanowił, że tym razem zabłyśnie na nielubianym przez siebie przedmiocie i napisze program który szybko za niego wszystko policzy. Przy okazji potrenuje do zbliżającej się wielkimi krokami Olimpiady Informatycznej.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite, kolejno: 1<=d<=10⁹ oraz 1<=n<=10⁵ które oznaczają kolejno długość pręta w milimetrach oraz liczbę kropel kwasu upuszczonych na niego. Każdy z kolejnych n wierszy zawiera dwie liczby całkowite, kolejno: 0<=x<=d oraz 0<=t<=10⁹. Liczba x oznacza odległość spuszczonej kropli w milimetrach od lewego końca metalu, a liczba t - moment upuszczenia kropli na pręt, mierzony w sekundach od początku eksperymentu.

Wyjście

W jedynym wierszu wyjścia należy wypisać najmniejszą całkowitą liczbę sekund od początku eksperymentu do momentu, w którym cały metal będzie pokryty rdzą.

Przykład

Wejście:
10 4
2 0
8 1
5 1
7 4

Wyjście:
3

Wyjaśnienie do przykładu:

Po pierwszej sekundzie eksperymentu rdzą będzie pokryty fragment od 1 do 3 milimetra metalu, po drugiej fragment od początku do 6 milimetra i od 7 do 9 milimetra.