Skoczki

Limit pamięci: 32 MB

Dana jest szachownica o wymiarach , z której usunięto pewną liczbę pól. Należy wyznaczyć maksymalną liczbę skoczków (koników) szachowych, które można ustawić na pozostałych polach szachownicy tak, żeby żadne dwa skoczki nie atakowały się nawzajem.

Rysunek 1: Skoczek umieszczony w polu S atakuje pola oznaczone przez x.

Zadanie

Napisz program, który:

• wczyta opis szachownicy z usuniętymi polami ze standardowego wejścia,
• wyznaczy maksymalną liczbę wzajemnie nie atakujących się skoczków szachowych, które można ustawić na tej szachownicy,
• zapisze wynik na standardowym wyjściu.

Wejście

W pierwszym wierszu znajdują się dwie liczby całkowite i , gdzie , . Liczba oznacza rozmiar szachownicy, a oznacza liczbę usuniętych pól.

W każdym z kolejnych wierszy jest zapisana para liczb naturalnych i , gdzie , oddzielonych pojedynczym odstępem. Są to współrzędne usuniętych pól. Lewy górny róg szachownicy ma współrzędne , natomiast prawy dolny róg ma współrzędne . Pola nie powtarzają się.

Wyjście

Na standardowym wyjściu należy zapisać dokładnie jeden wiersz, zawierający pojedynczą liczbę całkowitą równą maksymalnej liczbie wzajemnie nie atakujących się skoczków, które można ustawić na zadanej szachownicy.

Przykład

Dla danych wejściowych:

3 2
1 1
3 3

poprawną odpowiedzią jest:

5