Gitara

Ο Darko έχει έναν νέο φανταστικό εξωγήινο φίλο με ένα δισεκατομμύριο δάχτυλα. Ο εξωγήινος πήρε σύντομα την κιθάρα του, βρήκε μια απλή μελωδία στο διαδίκτυο και άρχισε να την παίζει.

Η κιθάρα, ως συνήθως, έχει έξι χορδές που συμβολίζονται με τους αριθμούς 1 έως 6. Κάθε χορδή χωρίζεται σε ~P~ τάστα (frets) που συμβολίζονται με τους αριθμούς 1 έως ~P~.

Μια μελωδία είναι μια ακολουθία ήχων, όπου κάθε τόνος παράγεται επιλέγοντας μια χορδή που πιέζεται σε ένα συγκεκριμένο τάστο (π.χ. 4η χορδή που πατιέται στο 8ο τάστο). Εάν μια χορδή πιέζεται σε πολλά τάστα, ο τόνος που παράγεται θα είναι αυτός που αντιστοιχεί στο υψηλότερο από αυτά τα τάστα.

Για παράδειγμα, εάν η 3η χορδή έχει ήδη πατηθεί στο 5ο τάστο και πρόκειται να δημιουργηθεί ο τόνος που αντιστοιχεί στο 7ο τάστο, η χορδή μπορεί να πατηθεί στο 7ο τάστο και να επιλεγεί χωρίς να απελευθερωθεί το 5ο τάστο, αφού μόνο το υψηλότερο επηρεάζει τον τόνο που παράγεται (7ος σε αυτήν την περίπτωση). Παρομοίως, εάν ο επόμενος τόνος να παραχθεί αντιστοιχεί στο 2ο τάστο της ίδιας χορδής, είναι απαραίτητο να απελευθερώσετε και το 5ο και το 7ο τάστο.

Γράψτε ένα πρόγραμμα που να υπολογίζει τον ελάχιστο αριθμό κινήσεων των δακτύλων που απαιτούνται για την παραγωγή της δεδομένης μελωδίας. Σημειώστε ότι το πάτημα ή η απελευθέρωση ενός μεμονωμένου τάστου μετράει ως κίνηση ενός δακτύλου. Το μάζεμα χορδών δεν μετράει ως κίνηση του δακτύλου, αλλά μάλλον ως κίνηση επιλογής κιθάρας.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο θετικούς ακέραιους που χωρίζονται από ένα μόνο διάστημα, ~N\;(N \leq 500\,000)~ και ~P\;(2 \leq P \leq 300\,000)~. Αντιπροσωπεύουν τον αριθμό των ήχων στη μελωδία και τον αριθμό των τάστα, αντίστοιχα.

Οι ακόλουθες ~N~ γραμμές περιγράφουν τα πεδία για τους αντίστοιχους τόνους ~-~ τη διάταξη της χορδής και τη διάταξη του τάστου, αντίστοιχα, με την ίδια σειρά που τους παίζει ο εξωγήινος.

Έξοδος

Σε μία μόνο γραμμή εξόδου, εκτυπώστε τον ελάχιστο αριθμό κινήσεων των δακτύλων.

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

input

5 15
2 8
2 10
2 12
2 10
2 5

output

7

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

Όλοι οι τόνοι που παίζονται παράγονται επιλέγοντας τη 2η χορδή. Αρχικά, πιέζονται τα τάστα 8, 10, 12, με τη σειρά (τρεις κινήσεις). Στη συνέχεια, το 12ο τάστο απελευθερώνεται για να παράγει ξανά τον δεύτερο τόνο (τέταρτη κίνηση). Τέλος, πιέζεται το 5ο τάστο και ακολουθεί η απελευθέρωση των τάστων 10 και 12 (συνολικά επτά κινήσεις).

input

7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

output

9

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

1, 1, 1, 1, 3, 0, 2 κινήσεις των δακτύλων είναι απαραίτητες, με τη σειρά των επτά τόνων που παράγονται.