Problem description

Bajtek ma planszę rozmiaru N × N podzieloną na N² pól. K prostokątnych obszarów na planszy jest pomalowanych na czarno, reszta planszy jest pomalowana na biało. Prostokątne obszary mają boki równoległe do boków planszy i przebiegające wzdłuż linii podziału planszy – każde pole planszy jest w obszarze albo w całości, albo wcale. Obszary nie przecinają się ze sobą. Wiersze i kolumny planszy są ponumerowane liczbami od 1 do N – wiersze od góry do dołu, a kolumny od lewej do prawej.

Planszę nazywamy szachownicą, jeżeli można ją podzielić na identyczne kwadraty o boku nie mniejszym od 1 i ściśle mniejszym od N, w taki sposób, że wszystkie pola wewnątrz każdego z tych kwadratów są tego samego koloru, a dwa sąsiednie kwadraty mają różne kolory. Dwa kwadraty nazywamy sąsiednimi, jeżeli mają wspólny bok. Poniżej pokazane są wszystkie możliwe szachownice dla N = 6:

Bajtek chce zamienić swoją planszę w szachownicę. W tym celu może on przemalowywać pola – jeśli pole było białe, po przemalowaniu staje się czarne i na odwrót. Pomóż Bajtkowi wyznaczyć najmniejszą liczbę przemalowań, jakich musi on dokonać, aby plansza stała się szachownicą.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i K – rozmiar planszy oraz liczba czarnych prostokątnych obszarów.

W każdym z kolejnych K wierszy znajdują się cztery liczby całkowite x₁, y₁, x₂, y₂ oddzielone pojedynczymi odstępami – odpowiednio numer wiersza i kolumny lewego górnego pola oraz numer wiersza i kolumny prawego dolnego pola prostokątnego obszaru.

Możesz założyć, że żadne dwa obszary się nie przecinają.

Wyjście

Twój program powinien wypisać jedną liczbę całkowitą – najmniejszą liczbę przemalowań potrzebnych, aby plansza stała się szachownicą.

Ograniczenia

2 ≤ N ≤ 10⁵.
0 ≤ K ≤ min (N²,10⁵).
1 ≤ x₁ ≤ x₂ ≤ N, 1 ≤ y₁ ≤ y₂ ≤ N.

Podzadania

Przykład

2 0

2

6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6

14

4 1
4 1 4 4

8