rt

#include<bits/stdc++.h>
#define N 40005
#define M 40005
using namespace std;
int sum,n,m,s,t,a[205][205];
int tot=2,head[N];
struct edge{
	int to,next,w;
}e[M*20];
void add(int u,int v,int w)
{
	e[tot]=(edge){v,head[u],w};
	head[u]=tot++;
}
int pre[N],dis[N];
int q[N],l,r;
bool bfs()
{
	l=r=0;
	fill(dis,dis+1+t+1,-1);
	q[++r]=s;
	dis[s]=0;
	pre[s]=head[s];
	while(l<r)
	{
		int now=q[++l];
		for(int i=head[now];i;i=e[i].next)
		{
			int to=e[i].to;
			if(e[i].w&&dis[to]==-1)
			{
				dis[to]=dis[now]+1;
				q[++r]=to;
				pre[to]=head[to];
				if(to==t) return 1;
			} 
		}
	}
	return 0;
}
int dfs(int x,int sum)
{
	if(x==t) return sum;
	int k,cnt=0;
	for(int i=pre[x];i&&sum;i=e[i].next)
	{
		pre[x]=i;
		int v=e[i].to;
		if(e[i].w&&dis[v]==dis[x]+1)
		{
			k=dfs(v,min(sum,e[i].w));
			if(k==0) dis[v]=1e9;
			e[i].w-=k;
			e[i^1].w+=k;
			sum-=k;
			cnt+=k;
		}
	}
	return cnt;
}
int Dinic()
{
	int ans=0;
	while(bfs()) ans+=dfs(s,1e9);
	return ans;
}
int id(int x,int y)
{
	return x*(n-1)+y;
}
int dx[]={1,1,-1,-1,2,2,-2,-2},dy[]={2,-2,2,-2,1,-1,1,-1};
int main()
{
	freopen("a.in","r",stdin);
	scanf("%d%d",&n,&m);
	s=0,t=n*n+1;
	sum=n*n;
	while(m--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if(!a[u][v])sum--;
		a[u][v]=1;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]) continue;
			if((i+j)&1) add(s,id(i,j),1),add(id(i,j),s,0);
			else add(id(i,j),t,1),add(t,id(i,j),0);
		}	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(((i+j)&1)==0||a[i][j]) continue;
			for(int k=0;k<8;k++)
			{
				int x=i+dx[k],y=j+dy[k];
				if(x<1||y<1||x>n||y>n||a[x][y]) continue;
				add(id(i,j),id(x,y),1),add(id(x,y),id(i,j),0);
			}
		}		
	printf("%d",sum-Dinic());
	return 0; 
}
/*
3 2
1 2
3 1
*/