#include<bits/stdc++.h>
#define maxn 1000001
#define INF 119260817
using namespace std;
int cnt,c[maxn],fr[maxn],to[maxn],Next[maxn],head[maxn],dis[maxn],vis[maxn],f[maxn],l[maxn],mf,qwq[505][505],x[8]={1,1,-1,-1,2,2,-2,-2},y[8]={2,-2,2,-2,1,-1,1,-1},s,t,n,m; 
queue<int>q;
int arr(int x,int y){
    return (x-1)*n+y;
}
void add(int x,int y,int z){    
    cnt++;
    c[cnt]=z;
    fr[cnt]=x;
    to[cnt]=y;
    Next[cnt]=head[x];
    head[x]=cnt;
}
int bfs(int S,int T){          
    for(int i=0;i<=n*n+1;i++)
        l[i]=0,vis[i]=-1;
    q.push(S);
    dis[S]=0;
    vis[S]=1;
    f[S]=INF;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=Next[i]){
            int v=to[i];
            if(c[i]&&vis[v]==-1){    
                f[v]=min(f[u],c[i]);   
                l[v]=i;               
                q.push(v);
                vis[v]=u;
            }
        }
    }if(vis[T]!=-1)return 1;          
    return 0;
}
void u(int S,int T){         
    int now=T;
    while(now!=S){
        int i=l[now];
        c[i]-=f[T];
        c[i^1]+=f[T];  
        now=fr[i];        
    }
    mf+=f[T];    
}
int main(){
    cnt=1;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    s=0;
    t=n*n+1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        qwq[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!qwq[i][j]){
                if((i+j)&1){
                    add(s,arr(i,j),1);
                    add(arr(i,j),s,0);
                }
                else
                    {
                    add(arr(i,j),t,1);
                    add(t,arr(i,j),0);
                }
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(((i+j)&1)==0)continue;
            for(int k=0;k<8;k++){
                int tox=i+x[k],toy=j+y[k];
                if(tox>=1&&tox<=n&&toy>=1&&toy<=n&&!qwq[tox][toy]){
                    add(arr(i,j),arr(tox,toy),INF);
                    add(arr(tox,toy),arr(i,j),0);
                }
            }
        }
    mf=0;
    while(bfs(s,t)==1)
        u(s,t);
    printf("%d\n",n*n-m-mf);
    return 0;
}