//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse2,avx")
#include <bits/stdc++.h>
#define ll int
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
using namespace std;
void dout() {
cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
cerr << H << ' ';
dout(T...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e18, N = 1e5 + 3;
struct rect {
int x = 0, y = 0, x2 = 0, y2 = 0;
};
int n, k, ans = inf, p[2][N], A, Z, S, W, B, L;
vector <rect> v;
int color(int x, int y) {
int z = (x - 1) / A;
int w = (y - 1) / A;
return ((z + w + Z) & 1);
}
int num(int x) {
int z = (x - 1) / A;
return (z & 1);
}
int getL() {
int x = n / A;
int a = ((x + 1) / 2) * A * A;
int b = (x / 2) * A * A;
int res = ((x + 1) / 2) * a + (x / 2) * b;
if (Z == 0) {
return res;
} else {
return n * n - res;
}
}
int getval(int x, int a, int b) {
if (x < 1) {
return 0;
}
int res = 0;
int last = ((x - 1) / A) * A + 1;
if (num(last) == 0) {
res += (x - last + 1) * a;
} else {
res += (x - last + 1) * b;
}
int q = (last - 1) / A;
res += ((q + 1) / 2) * A * a;
res += (q / 2) * A * b;
return res;
}
int getans() {
for (int i = 1; i <= n; i++) {
p[0][i] = p[0][i - 1];
p[1][i] = p[1][i - 1];
if (color(i, 1)) {
p[0][i]++;
} else {
p[1][i]++;
}
}
int res = 0;
for (auto i : v) {
int x = i.x, y = i.y, x2 = i.x2, y2 = i.y2;
int v1 = p[0][x2] - p[0][x - 1];
int v2 = p[1][x2] - p[1][x - 1];
res += getval(y2, v1, v2) - getval(y - 1, v1, v2);
}
return res;
}
void solve(int tc) {
cin >> n >> k;
for (int i = 0; i < k; i++) {
rect tmp;
cin >> tmp.x >> tmp.y >> tmp.x2 >> tmp.y2;
S += (tmp.x2 - tmp.x + 1) * (tmp.y2 - tmp.y + 1);
v.pb(tmp);
}
vector <int> factors = {};
for (int i = 1; i < n; i++) {
if (n % i == 0) {
factors.pb(i);
}
}
assert(factors.size() <= 96);
for (auto i : factors) {
A = i;
for (int j = 0; j < 2; j++) {
Z = j;
L = getL();
W = getans();
B = L - (S - W);
ans = min(ans, W + B);
}
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc = 1;
// cin >> tc;
for (int i = 0; i < tc; i++) {
solve(i);
// cleanup();
}
}
