Loop Town

Ορισμένες πόλεις έχουν πολύπλοκα οδικά δίκτυα που απαιτούν προηγμένη θεωρία γραφημάτων για να τα αναλύσουμε. Αλλά όχι η Loop Town! Η Loop Town έχει έναν μόνο κυκλικό δρόμο που περιστρέφεται γύρω από την πόλη. 'Εχει ~N~ κατοίκους που ζουν σε ~N~ ξεχωριστά σπίτια που βρίσκονται γύρω από το δρόμο. Η πόλη έχει επίσης ~N~ γραφεία, και κάθε κάτοικος εργάζεται σε ένα ξεχωριστό γραφείο.

Ο δρόμος στη Loop Town έχει μήκος ~L~. Η τοποθεσία κάθε κτιρίου θα αντιπροσωπεύεται από έναν ακέραιο μεταξύ του ~0~ και του ~L~ - ~1~. Επειδή ο δρόμος είναι κυκλικός, οι θέσεις ~0~ και ~L~ - ~1~ είναι γειτονικές. Είναι εγγυημένο ότι οι θέσεις όλων των ~2N~ κτιρίων θα είναι μοναδικές.

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

Ωστόσο, μια πανδημία έχει έρθει τώρα στη Loop Town, διαταράσσοντας αυτή τη συνηθισμένη ρουτίνα. Για να αποτραπεί η εξάπλωσης της ασθένειας, οι κάτοικοι πρέπει τώρα να τηρούν την κοινωνική απόσταση όταν πηγαίνουν με τα πόδια στη δουλειά. Δεδομένου ότι ο δρόμος με βρόχο (loop) είναι σχετικά στενός, αυτό σημαίνει ότι είναι πολύ πιο άβολο για δύο άτομα να διασταυρώσουν ο ένας τον άλλον στο δρόμο για τη δουλειά (ένα άτομο πρέπει να αποχωρήσει προσωρινά από το μονοπάτι για να περάσει ο άλλος). Ποιος είναι ο ελάχιστος συνολικός αριθμός διασταυρώσεων των κατοίκων, υποθέτοντας ότι όλοι οι κάτοικοι συνεργάζονται για να το πετύχουν αυτό;

Είσοδος

Η πρώτη γραμμή περιέχει τους δύο ακέραιους ~N~ και ~L~ (~1~ ~\le~ ~N~ ~\le~ ~1\,000\,000~, ~1~ ~\le~ ~L~ ~\le~ ~10^9~).

Η ~i~-οστη από τις επόμενες ~N~ γραμμές περιέχει τους δύο ακέραιους ~a_i~ και ~b_i~ (~0~ ~\le~ ~a_i~, ~b_i~ ~<~ ~L~), όπου ~a_i~ και ~b_i~ αντιπροσωπεύουν τις τοποθεσίες του σπιτιού και του γραφείου του ~i~-οστου κατοίκου αντίστοιχα. Είναι δεδομένο ότι όλες οι ~2N~ τοποθεσίες είναι μοναδικές.

Βαθμολογία

Για ~12~ από τρυς ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~5\,000~.

Για επιπλέον ~6~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~100\,000~.

Έξοδος

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

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

input

3 100
10 50
30 20
60 40

output

0

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

Μιας και ο δρόμος είναι κυκλικός, κανένας δεν χρειάζεται να διασταυρωθεί με κανέναν.

input

4 100
30 70
10 12
60 75
90 50

output

1