#include"bits/stdc++.h"
using namespace std;
#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;(a)<=i;i--)
#define R0F(i,a)ROF(i,0,a)
#define rep(a)F0R(_,a)
#define each(a,x)for(auto&a:x)
#define all(a)begin(a),end(a)
#define sz(x)int(size(x))
#define lla(x)rbegin(x),rend(x)
#define SUM(a)accumulate(all(a),0ll)
#define SUMM(a,b)accumulate(a,a+b,0ll)
#define MAX(a)(*max_element(all(a)))
#define MAXX(a,b)(*max_element(a,a+b))
#define MIN(a)(*min_element(all(a)))
#define MINN(a,b)(*min_element(a,a+b))
#define con const int
#ifdef LOCAL
#define print(x)cout<<x
#else
#define print(x)
#endif
using ld=long double;
using ll=long long;
using str=string;
template<class T,class U>ifstream&operator>>(istream&in,pair<T,U>a){return in>>a.first>>a.second;}
void fileset(str a){freopen((a+".in").c_str(),"r",stdin);freopen((a+".out").c_str(),"w",stdout);}

ll cnt[2];

int main(){
    int N, K;
    cin >> N >> K;

    cnt[1] = 2ll * (N / 2) * (N / 2 + 1);
    cnt[0] = 1ll * (N / 2 + 1) * (N / 2 + 1) + 1ll * (N / 2) * (N / 2);

    rep(K){
	int X, Y;
	cin >> X >> Y;

	if (X & 1){
	    if (Y & 1){
		cnt[0] --;
		cnt[1] ++;
	    } else {
		cnt[1] --;
		cnt[0] ++;
	    }
	} else {
	    if (Y & 1){
		cnt[1] --;
		cnt[0] ++;
	    } else {
		cnt[0] --;
		cnt[1] ++;
	    }
	}
    }

    ll ans = LLONG_MAX;

    if (0 == (N & 1)){
	ans = 1ll * N * N / 2;
    }

    if (0 == K){
	for (int i = 1; i < N; i ++){
	    if (0 == N % i){
		int j = N / i;
		if (j & 1){
		    ll x = 1ll * i * i * (j / 2);
		    ll y = 1ll * i * i * (j / 2 + 1);

		    ans = min(ans, y * (j / 2) + x * (j / 2 + 1));
		}
	    }
	}
    }

    if (0 == K){
	cout << ans << endl;
    } else {
	cout << MINN(cnt, 2) << endl;
    }
}