Square Pool

Ο Ron θέλει να χτίσει μια τετράγωνη πισίνα στην τετράγωνη αυλή του ~N \times N~ διαστάσεων, αλλά η αυλή του περιέχει ~T~ δέντρα. Η δουλειά σας είναι να προσδιορίσετε το μήκος πλευράς, της μεγαλύτερης τετράγωνης πισίνας που μπορεί να κατασκευάσει.

Είσοδος

Η πρώτη γραμμή εισόδου θα περιέχει έναν ακέραιο αριθμό ~N~, ~N \ge 2~. Η δεύτερη γραμμή θα περιέχει τον θετικό ακέραιο ~T~ όπου ~T < N^{2}~. Η υπόλοιπη είσοδος θα αποτελείται από ~T~ γραμμές, καθεμία από τις οποίες θα αντιπροσωπεύει τη θέση ενός δέντρου. Η θέση δίνεται από δύο θετικούς ακέραιους αριθμούς, τον ~R~ ακολουθούμενο από τον ~C~, χωρισμένους με ένα κενό διάστημα. Κάθε δέντρο βρίσκεται στη γραμμή ~R~ και στη στήλη ~C~, όπου οι γραμμές αριθμούνται από πάνω προς τα κάτω από το ~1~ έως το ~N~ και οι στήλες αριθμούνται από αριστερά προς τα δεξιά από το ~1~ έως το ~N~. Κανένα δέντρο δεν βρίσκεται στην ίδια θέση με ένα άλλο.

Ο ακόλουθος πίνακας δείχνει πώς κατανέμονται οι ~15~ διαθέσιμοι βαθμοί.

Βαθμοί	Μήκος/Πλάτος Αυλής	Αριθμός Δέντρων
~3~ βαθμοί	~N \le 50~	~T = 1~
~5~ βαθμοί	~N \le 50~	~T \le 10~
~4~ βαθμοί	~N \le 500000~	~T \le 10~
~3~ βαθμός	~N \le 500000~	~T \le 100~

Έξοδος

Εξάγετε μια γραμμή που να περιέχει τον ~M~, τον μεγαλύτερο θετικό ακέραιο αριθμό, τέτοιο ώστε ένα τετράγωνο ~M \times M~ διαστάσεων να περιέχεται ολόκληρο στην αυλή του Ron, χωρίς να περιέχει κανένα από τα ~T~ δέντρα.

Παραδείγματα

input

5
1
2 4

output

3

Επεξήγηση του πρώτου παραδείγματος:

Μια εικόνα της αυλής δίνεται παρακάτω. Η θέση του δέντρου επισημαίνεται από 🌲 και επισημαίνεται επίσης ένα από τα πολλά ~3 \times 3~ τετράγωνα που δεν περιέχουν το δέντρο. Όλα τα μεγαλύτερα τετράγωνα περιέχουν το δέντρο.

input

15
8
4 7
4 1
14 11
10 6
13 4
4 10
10 3
9 14

output

7

Επεξήγηση του δεύτερου παραδείγματος:

Μια εικόνα της αυλής δίνεται παρακάτω.Η θέση κάθε δέντρου επισημαίνεται με ένα 🌲 και επισημαίνεται επίσης ένα από τα διάφορα ~7 \times 7~ τετράγωνα που δεν περιέχουν δέντρο. Όλα τα μεγαλύτερα τετράγωνα περιέχουν ένα δέντρο.