#include<bits/stdc++.h>
#define int long long
#define N 80005
#define M 320005
#define _ make_pair
using namespace std;
struct ljb{
	int en,v[2*M],w[2*M],fst[N],nxt[2*M];
	inline void add(int x,int y,int z)
	{
	//	cout<<x<<"--("<<z<<")-->"<<y<<endl;
		en++;
		v[en]=y;
		w[en]=z;
		nxt[en]=fst[x];
		fst[x]=en;
	}
}; 
ljb g;
int n,m,s=1,t,ans,dis[N],dqh[N];
bool ban[405][405];
queue<pair<int,int> > qu;
inline int hsh(int x,int y){return x*n-n+y+1;}
inline void in(int x,int y,int z)
{g.add(x,y,z);g.add(y,x,0);}
inline void in2(int x,int y,int dx,int dy)
{
	if(x+dx<=0||x+dx>n||y+dy<=0||y+dy>n||ban[x+dx][y+dy]) return;
	in(hsh(x,y),hsh(x+dx,y+dy),1);
}
inline int cp(int x){return x&1?x+1:x-1;}
inline bool bfs()
{
	memset(dis,63,sizeof(dis));
	for(int i=1;i<=t;i++) dqh[i]=g.fst[i];
	while(!qu.empty()) qu.pop();
	qu.push(_(s,0));
	while(!qu.empty())
	{
		int now=qu.front().first,d=qu.front().second;
		qu.pop();
		if(dis[now]<1e18) continue;
		dis[now]=d;
		for(int i=g.fst[now];i;i=g.nxt[i])
		{
			int s=g.v[i],w=g.w[i];
		//	cout<<now<<"--"<<w<<"->"<<s<<endl;
			if(w>0) qu.push(_(s,d+1));
		}
	}
	return dis[t]<1e18;
}
inline int dfs(int x,int y)
{
	if(x==t) return y;
	int sy=y;
	for(int i=dqh[x];i;i=g.nxt[i])
	{
		int s=g.v[i],t=g.w[i];
		if(dis[s]<=dis[x]||t==0) continue;
		dqh[x]=i;
		int f=dfs(s,min(sy,t));
		g.w[i]-=f;
		g.w[cp(i)]+=f;
		sy-=f;
		if(sy<=0) break;
	}
	return y-sy;
}
signed main()
{
	cin>>n>>m;t=n*n+2;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		ban[x][y]=1;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(ban[i][j]==0)
			{
				if(((i+j)&1)==0)
				{
					in(1,hsh(i,j),1);
					in2(i,j,1,2);
					in2(i,j,-1,2);
					in2(i,j,1,-2);
					in2(i,j,-1,-2);
					in2(i,j,2,1);
					in2(i,j,-2,1);
					in2(i,j,2,-1);
					in2(i,j,-2,-1);
				}
				else in(hsh(i,j),t,1);
			}
	while(bfs()) ans+=dfs(s,1e18);
	cout<<n*n-m-ans;
	return 0;
}