#include<bits/stdc++.h> 
#define ask(x,y) x*(n-1)+y
#define int long long
const int inf=1e15;
using namespace std;
int n,m,s,t,x,y,z,tot,maxflow,maxn,num[5000005],dp[5000005],lst[5000005],head[5000005],ver[5000005],edge[5000005],nxt[5000005],d[200005],now[5000005];
bool flag[205][205];
void add(int x,int y,int z){
	ver[++tot]=y,lst[tot]=x,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
	ver[++tot]=x,lst[tot]=y,edge[tot]=0,nxt[tot]=head[y],head[y]=tot;
}
bool bfs(){
	memset(d,0,sizeof(d));
	queue<int> q;
	q.push(s),d[s]=1,now[s]=head[s];
	while(q.size()){
		int x=q.front();
//		cout<<x<<endl;
		q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			if(edge[i]&&!d[y]){
				q.push(y);
				now[y]=head[y];
				d[y]=d[x]+1;
				if(y==t) return 1;
			}
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t) return flow;
	int rest=flow;
	for(int i=now[x];i&&rest;i=nxt[i]){
		now[x]=i;
		int y=ver[i];
		if(edge[i]&&d[y]==d[x]+1){
			int k=dinic(y,min(rest,edge[i]));
			if(k==0) d[y]=0;
			edge[i]-=k,edge[i^1]+=k;
			rest-=k; 
		}
	}
	return flow-rest;
}
int dx[8]={-1,-2,2,1,-1,-2,2,1};
int dy[8]={-2,-1,-1,-2,2,1,1,2};
signed main(){
	tot=1;
	cin>>n>>m;
	s=0,t=n*n+1;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		flag[x][y]=1;
	} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(flag[i][j]) continue;
			if(((i+j)&1)==1) add(s,ask(i,j),1);
			else add(ask(i,j),t,1);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(((i+j)&1)==0||flag[i][j]) continue;
			for(int k=0;k<8;k++){
				int fx=i+dx[k],fy=j+dy[k];
				if(fx<1||fy<1||fx>n||fy>n||flag[fx][fy]) continue;
				add(ask(i,j),ask(fx,fy),inf);
			}
		}
	}
	int flow=0;
	while(bfs()){
		while(flow=dinic(s,inf)) maxflow+=flow;
	}
	cout<<n*n-m-maxflow;
}