Wstęp do programowania w C++

Jasio właśnie został planistą odpowiedzialnym za planowanie seansów filmowych w kinie "Fraktal". Jasio ma do dyspozycji bardzo dużo sal kinowych i w związku z tym planowanie projekcji filmów jest bardzo proste. Jednak zastanawia się, jaki jest najdłuższy odstęp czasowy, w którym nie jest puszczany żeden film. Bardzo mu zależy, aby klienci kina nie musieli długo czekać na film. 

Wejście

W pierwszym wierszu jedna liczba d określająca liczbę sekund otwarcia kina (0 < d ≤ 10⁹).

W drugim wierszu jedna liczba n określająca liczbę seansów (0 < n ≤ 10⁶).

W kolejnych n wierszach po dwie liczby s i t określające sekundę, w której rozpoczął się film oraz czas trwania filmu liczoną w sekundach — film może się zakończyć po czasie zamknięcia kina (0 ≤ s ≤ d, 0 < t ≤ 10⁹)

Wyjście

Jedna liczba określająca maksymalną liczbę sekund, w której nie puszczany jest żaden film.

Przykład

Wejście:
10
3
0 4
1 5
9 10

Wyjście:
3