//代码略

//hzwer's code:

#include<iostream>

#include<cstdio>

#include<cstring>

#define INF 0x7fffffff

using namespace std;

int n,m,bl,wt,ans,cnt=;

bool del[][];

int mark[][];

int xx[]={,,,,-,-,-,-},

    yy[]={,-,,-,,-,,-};

struct data{int to,next,v;}e[];

int head[],h[];

void insert(int u,int v,int w)

{

     cnt++;

     e[cnt].to=v;

     e[cnt].next=head[u];

     head[u]=cnt;

     e[cnt].v=w;

     cnt++;

     e[cnt].to=u;

     e[cnt].next=head[v];

     head[v]=cnt;

 }

void build()

{

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

             if(del[i][j])continue;

             else if(mark[i][j]<bl)

             {

             for(int k=;k<;k++)

             {

                     int nowx=i+xx[k],nowy=j+yy[k];

                     if(nowx<||nowy<||nowx>n||nowy>n||del[nowx][nowy])continue;

                     insert(mark[i][j],mark[nowx][nowy],INF);

                     }

             insert(,mark[i][j],);

             }

             else insert(mark[i][j],wt,);

 }

bool bfs()

{

     int q[],t=,w=,i,now;

     memset(h,-,sizeof(h));

     h[]=q[]=;

     while(t<w)

     {

               now=q[t];t++;

               i=head[now];

               while(i)

               {

                       if(h[e[i].to]==-&&e[i].v){h[e[i].to]=h[now]+;q[w++]=e[i].to;}

                       i=e[i].next;

                       }

               }

     if(h[wt]==-)return ;

     return ;

 }

int dfs(int x,int f)

{

    if(x==wt)return f;

    int i=head[x];

    int w,used=;

    while(i)

    {

            if(e[i].v&&h[e[i].to]==h[x]+)

            {

                w=f-used;

                w=dfs(e[i].to,min(w,e[i].v));

                e[i].v-=w;

                e[i^].v+=w;

                used+=w;

                if(used==f)return f;

                }

                i=e[i].next;

            }

    if(!used)h[x]=-;

    return used;

    }

void dinic(){while(bfs()){ans+=dfs(,INF);}}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

    {

            int x,y;

            scanf("%d%d",&x,&y);

            del[x][y]=;

            }

    bl=,wt=(n*n+)/+;

    for(int i=;i<=n;i++)

       for(int j=;j<=n;j++)

          if((i+j)%==){mark[i][j]=bl;bl++;}

          else {mark[i][j]=wt;wt++;}

    build();

    dinic();

    printf("%d",n*n-m-ans);

    return ;

}