#include<bits/stdc++.h>
#define pos(i, j) ((i-1)*nn+j)
#define int long long
using namespace std;
inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x * f;
}
const int N = 500001, M = 1000001, inf = 7998244353;
const int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
const int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
struct Edge{
	int to, nxt;
	int w;
}e[M];
int tot = 1, head[N];
inline void add_edge(int u, int v, int w){
	tot++;
	e[tot].to = v;
	e[tot].nxt = head[u];
	e[tot].w = w;
	head[u] = tot;
	return;
}
inline void add(int u, int v, int w){
	//printf("add(%d,%d)\n", u, v);
	add_edge(u, v, w);
	add_edge(v, u, 0);
	return;
}
int n, s, t, dis[N], cur[N];
inline bool bfs(){
	for(int i = 1; i <= n; i++) dis[i] = inf;
	queue<int> q; q.push(s);
	cur[s] = head[s], dis[s] = 0;
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(int i = head[u]; i; i = e[i].nxt){
			int v = e[i].to;
			//cout << u << " " << v << " " << q.size() << endl;
			if(dis[v] == inf && e[i].w){
				cur[v] = head[v], dis[v] = dis[u] + 1;
				q.push(v);
				if(v == t) return true;
			}
		}
	}
	return false;
}
inline int dfs(int u, int sum){
	if(u == t) return sum;
	int res = 0;
	for(int i = cur[u]; i; i = e[i].nxt){
		int v = e[i].to;
		cur[u] = i;
		if(dis[v] == dis[u] + 1 && e[i].w){
			int k = dfs(v, min(sum, e[i].w));
			e[i].w -= k, e[i^1].w += k;
			res += k, sum -= k;
		}
	}
	return res;
}
inline int Dinic(){
	int ans = 0;
	while(bfs()){
		ans += dfs(s, inf);
	}
	return ans;
}
bool ban[201][201];
signed main(){
	int nn = read(), m = read();
	int mm = m;
	while(m--){
		int u = read(), v = read();
		ban[u][v] = true;
	}
	n = nn * nn + 2;
	s = nn * nn + 1;
	t = s + 1;
	for(int i = 1; i <= nn; i++){
		for(int j = 1; j <= nn; j++){
			if((i+j) & 1){
				add(s, pos(i, j), 1);
				if(!ban[i][j]){
					for(int k = 0; k < 8; k++){
						int xx = i + dx[k], yy = j + dy[k];
						if(xx >= 1 && xx <= nn && yy >= 1 && yy <= nn){
							//if(!ban[xx][yy]){
								add(pos(i, j), pos(xx, yy), inf);
							//}
						}
					}
				}
			}else{
				if(!ban[i][j]){
					add(pos(i, j), t, 1);
				}
			}
		}
	}
	cout << nn * nn - mm - Dinic() << endl;
	return 0;
}