Baltic Olympiad in Informatics: 2001 Day 2, Problem 1

We are given a chessboard of size ~n \times n~, from which some fields have been removed. The task is to determine the maximum number of knights that can be placed on the remaining fields of the board in such a way that none of them check each other.

Figure 1. A knight placed on the field ~S~ checks fields marked with ~X~.

Write a program that determines the maximum number of knights that can be placed on the chessboard in such a way that none of them can check each other.

Constraints

~1 \le n \le 200~

~0 \le m < n^2~

~1 \le x, y \le n~

Input Specification

The first line of input contains two space-separated integers ~n~ and ~m~, where ~n~ is the chessboard size and ~m~ is the number of removed fields.

Each of the following ~m~ lines contains two space-separated integers ~x~ and ~y~ — the coordinates of the removed fields. The coordinates of the upper left corner of the board are ~(1, 1)~, and of the bottom right are ~(n, n)~. The removed fields are not repeated in the input.

Output Specification

Output the maximum number of knights that can be placed on the given chessboard without checking each other.

Sample Input

3 2
1 1
3 3

Sample Output

5