// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii; typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i = 0; i < (n); ++i)
#define FOO(i,a,b) for(int i = (a); i <= (b); ++i)
#define AI(x) begin(x),end(x)
template<class I> bool chmax(I &a, I b){ return a < b ? (a = b, true) : false;}
template<class I> bool chmin(I &a, I b){ return a > b ? (a = b, true) : false;}
#ifdef OWO
#define debug(args...) LKJ("[ " + string(#args) + " ]", args)
void LKJ(){ cerr << endl;}
template<class I, class...T> void LKJ(I&&x, T&&...t){ cerr<<x<<", ", LKJ(t...);}
template<class I> void DE(I a, I b){ while(a < b) cerr << *a << " \n"[next(a) == b], ++a;}
#else
#define debug(...) 0
#define DE(...) 0
#endif
const int N = 1e5 + 1;
int n, k;
void findfac(int n, vector<int> &fac){
for(int i = 1; i * i <= n; ++i){
if(n % i != 0) continue;
fac.pb(i);
fac.pb(n / i);
}
sort(AI(fac));
fac.erase(unique(AI(fac)), end(fac));
if(fac.back() == n) fac.pop_back();
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
vector<int> facs;
findfac(n, facs);
// ca : has top left corner
// cb : does not
vector<ll> ca(facs.size());
vector<ll> cb(facs.size());
FOR(i,facs.size()){
int f = facs[i];
ll nn = n / f;
ll bc = (nn * nn + 1) / 2;
ca[i] = bc * f * f;
cb[i] = 1ll * n * n - ca[i];
}
FOR(_,k){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
--x1, --y1, --x2, --y2;
FOR(i, facs.size()){
int f = facs[i];
int lx = (x2 - x1 + 1);
int ly = (y2 - y1 + 1);
lx %= f * 2, ly %= f * 2;
if(lx == 0 or ly == 0) continue;
int xr = x1 + lx - 1, yr = y1 + ly - 1;
ll vx = 0, vy = 0;
int odd = ((x1 / f) & 1);
FOO(x, x1, xr){
if(((x / f) & 1) != odd) --vx;
else ++vx;
}
odd = ((y1 / f) & 1);
FOO(y, y1, yr){
if(((y / f) & 1) != odd)
vy -= vx;
else vy += vx;
}
if((x1 / f) + (y1 / f) & 1) vy *= 1;
else vy *= -1;
ca[i] += vy;
cb[i] -= vy;
}
}
DE(AI(facs));
DE(AI(ca));
DE(AI(cb));
cout << min(
*min_element(AI(ca)),
*min_element(AI(cb))
);
return 0;
}
