FRAKTAL - konkurs programistyczny

Dana jest plansza składająca się z n × m pól ułożonych w n rzędów, po m kolumn. W każdym rzędzie ustawiona jest nieparzysta liczba pionków. Na jednym polu ustawiony jest co najwyżej jeden pionek. W każdym rzędzie pionki zajmują sąsiadujące ze sobą pola.

W każdym rzędzie możesz wykonać 0 lub więcej ruchów. Dozwolone ruchy to:

1. Jeżeli po prawej stronie skrajnie prawego pionka jest wolne pole, to możesz przestawić skrajnie lewy pionek na to pole.
2. Jeżeli po lewej stronie skrajnie lewego pionka jest wolne pole, to możesz przestawić skrajnie prawy pionek na to pole.

Odpowiedz na pytanie, ile minimalnie ruchów trzeba wykonać żeby pionki były ustawione symetrycznie względem dowolnej z m kolumn?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [2, 10⁵] i m ∈ [2, 10⁵] określające rozmiary planszy. W kolejnych n liniach znajdują się opisy rzędów.

Opis każdego rzędu składa się z dwóch liczb całkowitych l i r (1 ≤ l ≤ r ≤ m) oznaczających, że w danym rzędzie pionki ustawione są w kolumnach od l do r (włącznie z nimi). Wartość l - r + 1 jest nieparzysta.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, ile minimalnie ruchów trzeba wykonać żeby pionki były ustawione symetrycznie względem dowolnej z m kolumn.

Przykład

Wejście:

7 8
1 3
1 1
2 6
3 3
2 4
1 7
3 7

Wyjście:

8

Wyjaśnienie do przykładu:

Minimalną liczbę ruchów uzyskamy ustawiając pionki symetrycznie względem 4 kolumny.

• W 1 rzędzie wykonujemy 2 ruchy w prawo.
• W 2 rzędzie wykonujemy 3 ruchy w prawo.
• W 4 rzędzie wykonujemy 1 ruch w prawo.
• W 5 rzędzie wykonujemy 1 ruch w prawo.
• W 7 rzędzie wykonujemy 1 ruch w lewo.