#include <iostream>

using namespace std;

const int N = 205, dx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
int n, m, tot, T, link[N * N], road[N * N], cnt, nums[N][N];
bool ban[N][N], map[N * N][N * N];

bool Find(int v)
{
	for (int i = 1; i <= tot; i ++ )
	{
		if (map[v][i] && road[i] != T)
		{
			road[i] = T;
			if (link[i] == 0 || Find(link[i]))
			{
				link[i] = v;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int x, y, i = 1; i <= m; i ++ )
	{
		scanf("%d%d", &x, &y);
		ban[x][y] = 1;
	}
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j ++ )
			if (!ban[i][j]) nums[i][j] = ++ tot;
	
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= n; j ++ )
		{
			if (ban[i][j]) continue;
			for (int x, y, k = 1; k <= 8; k ++ )
			{
				x = i + dx[k];y = j + dy[k];
				if (x >= 1 && x <= n && y >= 1 && y <= n && !ban[x][y])
				{
					map[nums[i][j]][nums[x][y]] = true;
				}
			}
		}
	}
	
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= n; j ++ )
		{
			if (!ban[i][j] && (i + j) % 2)
			{
				T ++ ;
				if (Find(nums[i][j])) cnt ++ ;
			}
		}
	}
	
	printf("%d\n", tot - cnt);
	return 0;
}