33ος ΠΔΠ Καμπ (κοινά)
CANDYSTRIPE2 (candystripe2)

Έχουμε (και πάλι¹) \(N\) σοκολατάκια, αριθμημένα από \(1\) έως και \(N\), συσκευασμένα και τοποθετημένα στη σειρά το ένα δίπλα στο άλλο σε μία ταινία. Κάποια από αυτά έχουν πικρή σοκολάτα και κάποια έχουν γλυκιά σοκολάτα. Επειδή ο αδερφός μας έχει μια απέχθεια για την πικρή σοκολάτα, κάναμε ιδιαίτερη παραγγελία στο ζαχαροπλαστείο και ζητήσαμε η ταινία να έχει λίγα πικρά σοκολατάκια και πολλά γλυκά.

Σαν απόδειξη ότι εκπλήρωσε την επιθυμία μας, το ζαχαροπλαστείο μάς απαριθμεί ένα σύνολο από \(M\) τμήματα της ταινίας, καθένα από τα οποία περιγράφεται από δύο αριθμούς \(L_i\) και \(R_i\) και περιέχει τα σοκολατάκια από τη θέση \(L_i\) μέχρι τη και τη θέση \(R_i\) (συμπεριλαμβανομένων). Μας εγγυάται ότι σε κάθε ένα από αυτά τα τμήματα υπάρχει ακριβώς ένα πικρό σοκολατάκι.

Αν οι εγγυήσεις του ζαχαροπλαστείου είναι αληθείς, βρείτε πόσα είναι τα περισσότερα πικρά σοκολατάκια που μπορεί να υπάρχουν στην ταινία.

Αρχεία Εισόδου (candystripe2.in):

Η πρώτη γραμμή της εισόδου θα περιέχει δύο θετικούς ακέραιους αριθμούς \(N\) και \(M\), χωρισμένους με ένα κενό διάστημα: το μέγεθος της ταινίας και το πλήθος των τμημάτων που απαριθμεί το ζαχαροπλαστείο. Κάθε μία από τις επόμενες \(M\) γραμμές αντιστοιχεί σε ένα απαριθμημένο τμήμα περιέχει δύο ακέραιους, \(L_i\) και \(R_i\), χωρισμένους μεταξύ τους με ένα κενό διάστημα.

Αρχεία Εξόδου (candystripe2.out):

Η έξοδος πρέπει να περιέχει μία γραμμή με ακριβώς έναν ακέραιο αριθμό: πόσα είναι τα περισσότερα πικρά σοκολατάκια που μπορεί να υπάρχουν στην ταινία, αν είναι αληθείς οι εγγυήσεις του ζαχαροπλαστείου. Αν δεν υπάρχει απάντηση που να είναι συνεπής με τις εγγυήσεις του ζαχαροπλαστείου, η έξοδος πρέπει να περιέχει τον αριθμό \(−1\).

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1^o

candystripe2.in	candystripe2.out
5 3 3 4 1 4 2 5	1

Εξήγηση 1^ου παραδείγματος: Στο πρώτο παράδειγμα, μπορεί να υπάρχει μόνο ένα πικρό σοκολατάκι, είτε στη θέση \(3\) ή στη θέση \(4\).

2^o

candystripe2.in	candystripe2.out
6 2 2 4 3 5	4

Εξήγηση 2^ου παραδείγματος: Στο δεύτερο, μπορούν να υπάρχουν τέσσερα πικρά σοκολατάκια, στις θέσεις \(1\), \(2\), \(5\) και \(6\).

3^o

candystripe2.in	candystripe2.out
4 3 1 4 2 2 3 3	-1

Εξήγηση 3^ου παραδείγματος: Στο τρίτο παράδειγμα, τα δύο τελευταία τμήματα εγγυώνται ότι υπάρχουν πικρά σοκολατάκια στις θέσεις \(2\) και \(3\). Όμως, το πρώτο τμήμα εγγυάται ότι υπάρχει μόνο ένα πικρό σοκολατάκι μεταξύ των θέσεων \(1\) και \(4\). Αυτά δεν μπορούν να είναι συγχρόνως αληθή.

Περιορισμοί:

\(1 \leq N \leq 200.000\) και \(1 \leq M \leq 100.000\).
\(1 \leq L_i \leq R_i \leq N\).
Όριο χρόνου εκτέλεσης: \(1\) sec.
Όριο μνήμης: \(64\) MB.

Subtasks

Για περιπτώσεις ελέγχου συνολικής αξίας 10%, θα είναι \(N \leq 20\) και \(M \leq 20\).
Για περιπτώσεις ελέγχου συνολικής αξίας 30%, θα είναι \(N \leq 1.000\) και \(M \leq 2.000\).
Για περιπτώσεις ελέγχου συνολικής αξίας 60%, θα είναι \(N \leq 10.000\) και \(M \leq 10.000\).
Για περιπτώσεις ελέγχου συνολικής αξίας 65%, θα είναι \(\mathit{average}(R_i − L_i) \leq 20\)