#include <bits/stdc++.h>

using namespace std;

const int K = 205, N = K * K, M = N << 2;
const int D[][2] = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

int n, m, h[N], e[M], ne[M], cnt, a, b, t[N], v, y, r;
bool g[K][K], st[N];

void add(int x, int y)
{
    e[ne[cnt] = h[x], h[x] = cnt++] = y;
}

bool dfs(int x)
{
    for (int i = h[x], y; ~i; i = ne[i])
        if (!st[y = e[i]])
        {
            st[y] = 1;
            if (!~t[y] || dfs(t[y]))
            {
                t[y] = x;
                return 1;
            }
        }
    return 0;
}

int main()
{
    cin >> n >> m, memset(h, -1, sizeof h), memset(t, -1, sizeof t);
    for (int i = 0; i < m; i++) cin >> a >> b, g[a - 1][b - 1] = 1;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!g[i][j])
            {
                if (i + j & 1) continue;
                for (int k = 0; k < 8; k++)
                {
                    a = i + D[k][0], b = j + D[k][1];
                    if (0 <= a && a < n && 0 <= b && b < n && !g[a][b]) add(i * n + j, a * n + b);
                }
            }

    r = n * n - m;
    for (int i = 0; i < n * n; memset(st, 0, sizeof st), r -= dfs(i++));

    cout << r;

    return 0;
}