#include<cstdio>
#include<cstring>
using  namespace  std;
struct  node
{
    int  y,c,next,other;
}a[501000];int  len,last[100100],n,m,st,ed;
bool  v[100100];
int  zhuan(int  x,int  y){return  (x-1)*n+y;}
int  dx[]={-1,-2,-2,-1,1,2,2,1};
int  dy[]={-2,-1,1,2,2,1,-1,-2};
int  list[100100],head,tail,h[100100];
void  ins(int  x,int  y,int  c)
{
    len++;
    a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;
    len++;
    a[len].y=x;a[len].c=0;a[len].next=last[y];last[y]=len;
    a[len].other=len-1;a[len-1].other=len;
}
bool  bt()
{
    memset(h,0,sizeof(h));h[st]=1;
    head=1;tail=2;list[head]=st;
    while(head<tail)
    {
        int  x=list[head];
        for(int  k=last[x];k;k=a[k].next)
        {
            int  y=a[k].y;
            if(a[k].c>0  &&  h[y]==0)
            {
                h[y]=h[x]+1;
                list[tail++]=y;
            }
        }
        head++;
    }
    return  h[ed]!=0;
}
inline  int  mymin(int  x,int  y){return  x<y?x:y;}
int  find(int  x,int  f)
{
    if(x==ed)return  f;
    int  ans=0,t=0;
    for(int  k=last[x];k;k=a[k].next)
    {
        int  y=a[k].y;
        if(a[k].c>0  &&  ans<f  &&  h[y]==h[x]+1)
        {
            ans+=t=find(y,mymin(a[k].c,f-ans));
            a[k].c-=t;a[a[k].other].c+=t;
        }
    }
    if(ans==0)h[x]=0;
    return  ans;
}
int  main()
{
    scanf("%d%d",&n,&m);ed=n*n+1;
    for(int  i=1;i<=m;i++)
    {
        int  x,y;
        scanf("%d%d",&y,&x);
        v[zhuan(x,y)]=true;
    }
    for(int  i=1;i<=n;i++)
    {
        for(int  j=1;j<=n;j++)
        {
            int  xx=zhuan(i,j);
            if(v[xx]==false)
            {
                if(i%2!=j%2)
                {
                    ins(st,xx,1);
                    for(int  k=0;k<=7;k++)
                    {
                        int  xxx=i+dx[k],yyy=j+dy[k];
                        if(xxx>=1  &&  xxx<=n  &&  yyy>=1  &&  yyy<=n)
                        {
                            int  yy=zhuan(xxx,yyy);
                            if(v[yy]==false)
                            {
                            	ins(xx,yy,1);
							}
                            
                        }
                    }
                }
                else  ins(xx,ed,1);
            }
        }
    }
    int  ans=0;
    while(bt()==true)
	{
		ans+=find(st,999999999);
	}
    printf("%d\n",n*n-m-ans);
    return  0;
}