Se considera o suprafata patrata de dimensiune S x S (un patrat cu coltul stanga-jos in (0,0) si coltul dreapta-sus in (S,S)). Pe aceasta suprafata se afla K puncte , date prin coordonatele lor (X_i, Y_i).
Se cere latura maxima a unui patrat, cu laturile paralele cu axele de coordonate, complet inclus in suprafata data, in interiorul caruia sa nu se afle niciun arc (arcele au voie sa se afle pe laturile sau in colturile patratului, dar nu strict in interior).
- Date de intrare
- Pe prima linie se citesc doua numere intregi S si K. Pe urmatoarele K linii se citesc cate doua numere intregi X si Y, coordonatele fiecarui arc.
- Date de iesire
- Se afiseaza un singur numar intreg: latura maxima a unui astfel de patrat.
- Restrictii
- 1 <= S <= 100 1 <= K <= 6 0 <= X,Y <= S
Exemple
Exemplul 1
Intrare
100 5 48 47 64 27 54 28 80 83 92 36
Iesire
53
Exemplul 2
Intrare
10 1 0 0
Iesire
10