//Serene

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

using namespace std;

const int maxn=200*200+10,maxm=4*maxn+maxn;

int n,k,S,T,tot;

bool pl[maxn];

int aa;char cc;

int read() {

	aa=0;cc=getchar();

	while(cc<'0'||cc>'9') cc=getchar();

	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();

	return aa;

}

struct Node{

	int x,y,cap,flow;

}node[2*maxm];

int cur[maxn];

int fir[maxn],nxt[2*maxm],e=1;

void add(int x,int y,int z) {

	node[++e].x=x;node[e].y=y;node[e].cap=z; nxt[e]=fir[x];fir[x]=e;

	node[++e].x=y;node[e].y=x;node[e].cap=0; nxt[e]=fir[y];fir[y]=e;

}

int zz[maxn],dis[maxn],s=1,t=0;

bool BFS() {

	memset(dis,-1,sizeof(dis));

	dis[S]=0; s=1,t=0;zz[++t]=S;

	int x,y;

	while(s<=t) {

		x=zz[s];s++;

		for(y=fir[x];y;y=nxt[y]) {

			if(node[y].flow>=node[y].cap||dis[node[y].y]!=-1) continue;

			dis[node[y].y]=dis[x]+1;

			zz[++t]=node[y].y;

		}

	}

	return dis[T]!=-1;

}

int DFS(int pos,int maxf) {

	if(pos==T||!maxf) return maxf;

	int rs=0,now;

	for(int &y=cur[pos];y;y=nxt[y]) {

		if(node[y].flow>=node[y].cap||dis[node[y].y]!=dis[node[y].x]+1) continue;

		now=DFS(node[y].y,min(maxf,node[y].cap-node[y].flow));

		node[y].flow+=now;

		node[y^1].flow-=now;

		rs+=now;

		maxf-=now;

	}

	if(!rs) dis[pos]=-1;

	return rs;

}

int Dinic() {

	int rs=0;

	while(BFS()) {

		memcpy(cur,fir,sizeof(fir));

		rs+=DFS(S,0x3f3f3f3f);

	}

	return rs;

}

int main() {

	n=read();k=read();tot=n*n;

	int x,y; S=tot+1;T=S+1;

	for(int i=1;i<=k;++i) {

		x=read();y=read();

		tot--;

		pl[(x-1)*n+y]=1;

	}

	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {

		x=(i-1)*n+j;

		if(pl[x]) continue;

		if((i+j)%2==0) add(S,x,1); else add(x,T,1);

		for(int r=1;r<=2;++r) {

			if(i>r) {

				int rr=3-r;

				if(j>rr) {

					y=x-r*n-rr;

					if(!pl[y]) {

						if((i+j)%2==0) add(x,y,1); else add(y,x,1);

					}

				}

				if(j<=n-rr) {

					y=x-r*n+rr;

					if(!pl[y]) {

						if((i+j)%2==0) add(x,y,1); else add(y,x,1);

					}

				}

			}

		}

	}

	printf("%d",tot-Dinic());

	return 0;

}