AlgoLiga 2018

Franek potrafi przenosić się w czasie. Niestety nie ma żadnej kontroli nad tym, kiedy i dokąd się przeniesie. Wiadomo jednak, że zawsze, gdy następuje taki przeskok w czasie, Franek znika, gdy kończy się pewna pełna sekunda i pojawia się na początku jakiejś (niekoniecznie innej) sekundy.

Może oczywiście zajść sytuacja, że w pewnym okresie czasu żyć będzie jednocześnie dwóch (lub więcej) Franków w różnym wieku. Wiedząc jak długo żyje Franek oraz jakie dokładnie skoki w czasie wykonywał, można wyznaczyć o ile maksymalnie i o ile minimalnie młodszego siebie mógł spotkać w swoim życiu. Napisz program, który wyznaczy te dwie wartości. 

Wejście

W pierwszej linii liczba sekund, które przeżył Franek s (1 ≤ s ≤ 10⁹) oraz liczba wykonanych skoków w czasie k (0 ≤ k ≤ 10⁶). 

W kolejnych k liniach dane dotyczące pojedynczego skoku: dwie liczby całkowite a i b (–10⁹ ≤ a,b ≤ 10⁹). Pierwsza oznacza numer sekundy, na końcu której Franek znika. Druga, to numer sekundy, na początku której Franek się pojawia. 

Przyjmujemy, że Franek urodził się na początku sekundy numer 1, a sekundy przed narodzinami Franka numerujemy wstecz liczbami ujemnymi. Nie ma sekundy numer 0. 

Wyjście

Dwie liczby całkowite: maksymalna i minimalna różnica wieku (w sekundach) pomiędzy dwoma Frankami żyjącymi w tym samym czasie lub NIE jeśli przez całe życie Franek nie miał szans spotkać młodszego siebie.

Przykład

Wejście:
16 5
5 2
4 -4
-4 -4
1 -2
-2 6

Wyjście:
13 1