#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
vector<array<int, 4>> rect;
for (int i = 0; i < k; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
a--, b--, c--, d--;
rect.push_back({a, b, c, d});
}
auto Solve = [&](int s) -> long long {
long long res = 1ll * (n / s) * (n / s) / 2 * s * s;
if (n / s % 2 == 1) {
res += 1ll * s * s;
}
auto CountCorner = [&](int sx, int sy, int ex, int ey) -> long long {
if (sx > ex || sy > ey) return 0;
assert(sx / s == ex / s && sy / s == ey / s);
if ((sx / s + sy / s) & 1) {
return +1ll * (ex - sx + 1) * (ey - sy + 1);
} else {
return -1ll * (ex - sx + 1) * (ey - sy + 1);
}
return 0;
};
auto CountVertical = [&](int sx, int sy, int ex, int ey) -> long long {
if (sx > ex || sy > ey) return 0;
assert(sy / s == ey / s);
assert((ex - sx + 1) % s == 0);
int cnt = (ex - sx + 1) / s;
if (cnt & 1) {
if ((sx / s + sy / s) % 2 == 1) {
return +1ll * (ey - sy + 1) * s;
} else {
return -1ll * (ey - sy + 1) * s;
}
}
return 0;
};
auto CountHorizontal = [&](int sx, int sy, int ex, int ey) -> long long {
if (sx > ex || sy > ey) return 0;
assert(sx / s == ex / s);
assert((ey - sy + 1) % s == 0);
int cnt = (ey - sy + 1) / s;
if (cnt & 1) {
if ((sx / s + sy / s) % 2 == 1) {
return +1ll * (ex - sx + 1) * s;
} else {
return -1ll * (ex - sx + 1) * s;
}
}
return 0;
};
auto CountInside = [&](int sx, int sy, int ex, int ey) -> long long {
if (sx > ex || sy > ey) return 0;
int x = (ex - sx + 1) / s;
int y = (ey - sy + 1) / s;
if (x % 2 == 1 && y % 2 == 1) {
if ((sx / s + sy / s) % 2 == 1) {
return +1ll * s * s;
} else {
return -1ll * s * s;
}
}
return 0;
};
for (int i = 0; i < k; i++) {
if (rect[i][0] / s == rect[i][2] / s && rect[i][1] / s == rect[i][3] / s) {
res += CountCorner(rect[i][0], rect[i][1], rect[i][2], rect[i][3]);
} else if (rect[i][0] / s == rect[i][2] / s) {
int sy = (rect[i][1] + s - 1) / s;
int ey = (rect[i][3] + 1) / s;
res += CountCorner(rect[i][0], rect[i][1], rect[i][2], s * sy - 1);
res += CountCorner(rect[i][0], s * ey + 0, rect[i][2], rect[i][3]);
res += CountHorizontal(rect[i][0], s * sy + 0, rect[i][2], s * ey - 1);
} else if (rect[i][1] / s == rect[i][3] / s) {
int sx = (rect[i][0] + s - 1) / s;
int ex = (rect[i][2] + 1) / s;
res += CountCorner(rect[i][0], rect[i][1], s * sx - 1, rect[i][3]);
res += CountCorner(s * ex + 0, rect[i][1], rect[i][2], rect[i][3]);
res += CountVertical(s * sx + 0, rect[i][1], s * ex - 1, rect[i][3]);
} else {
int sx = (rect[i][0] + s - 1) / s;
int sy = (rect[i][1] + s - 1) / s;
int ex = (rect[i][2] + 1) / s;
int ey = (rect[i][3] + 1) / s;
res += CountCorner(rect[i][0], rect[i][1], s * sx - 1, s * sy - 1);
res += CountCorner(rect[i][0], s * ey + 0, s * sx - 1, rect[i][3]);
res += CountCorner(s * ex + 0, rect[i][1], rect[i][2], s * sy - 1);
res += CountCorner(s * ex + 0, s * ey + 0, rect[i][2], rect[i][3]);
res += CountHorizontal(rect[i][0], s * sy + 0, s * sx - 1, s * ey - 1);
res += CountHorizontal(s * ex + 0, s * sy + 0, rect[i][2], s * ey - 1);
res += CountVertical(s * sx + 0, rect[i][1], s * ex - 1, s * sy - 1);
res += CountVertical(s * sx + 0, s * ey + 0, s * ex - 1, rect[i][3]);
res += CountInside(s * sx + 0, s * sy + 0, s * ex - 1, s * ey - 1);
}
}
return min(res, 1ll * n * n - res);
};
long long ans = 1ll * n * n;
for (int i = 1; i < n; i++) {
if (n % i == 0) {
ans = min(ans, Solve(i));
}
}
cout << ans << "\n";
return 0;
}
