#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#define int ll
const int MAX_N = 300010;
int n, k;
vector<tuple<int,int,int,int>> subr;
ll calgood(int w, int x1, int y1, int x2, int y2) {
// {
// ll res = 0;
// for (int i = x1;i <= x2;++i)
// for (int j = y1;j <= y2;++j) {
// int need = (1^(i/w) ^ (j/w))&1;
// res += need;
// }
// return res;
// }
ll res = 0;
ll a = 0, b = 0, c = 0, d = 0;
auto cal = [&](ll l, ll r, ll ot) -> pair<ll,ll> {
ll a = 0, b = 0;
ll lid = l / w +1, rid = r / w - 1;
if (lid <= rid) {
ll even = (rid/2) - ((lid-1)/2), odd = rid-lid+1-even;
a += even * w;
b += odd * w;
}
{
ll L = l, R = min(r, lid * w - 1);
if (((1^(l/w))&1))
a += R-L+1;
else
b += R-L+1;
}
if (lid-1 != rid+1) {
ll L = max(l, (rid+1) * w), R = r;
if (((1^(r/w))&1))
a += R-L+1;
else
b += R-L+1;
}
// for (int i = l;i <= r;++i)
// if (((1^(i/w))&1))
// ++a;
// else
// ++b;
if (ot) swap(a, b);
return {a, b};
};
tie(a, b) = cal(x1, x2, y1/w);
tie(c, d) = cal(y1, y2, y1/w);
return a * c + b * d;
}
ll calcost(int wid) {
ll res = calgood(wid, 0, 0, n-1, n-1);
for (auto [x1, y1, x2, y2] : subr) {
ll area = 1ll * (x2-x1+1) * (y2-y1+1);
ll good = calgood(wid, x1, y1, x2, y2);
ll bad = area - good;
res -= good;
res += bad;
}
return min(res, 1ll * n * n - res);
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
DE(n, k);
//if (n > 1000) return -1;
subr.resize(k);
for (auto &[x1, y1, x2, y2] : subr)
cin >> x1 >> y1 >> x2 >> y2, --x1, --x2, --y1, --y2;
ll res = 1ll * n * n;
for (int i = 1;i < n;++i)
if (n % i == 0)
chmin(res, calcost(i));
cout << res << '\n';
}
