#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
#define f first
#define s second
#define int ll
using namespace std;
using ll = long long;
ll calc(pair<pair<int, int>, pair<int, int>> rec, int d, int par) {
auto p = rec;
assert (p.f.f >= 0 && p.f.s >= 0 && p.s.f >= 0 && p.s.s >= 0);
if (p.f.f > p.s.f || p.f.s > p.s.s) {
return 0;
}
int x1 = p.f.f/d;
int x2 = p.s.f/d;
int y1 = p.f.s/d;
int y2 = p.s.s/d;
if (p.f.f%d == 0 && p.f.s%d == 0 && p.s.f%d == d-1 && p.s.s%d == d-1) {
int tot = (x2 - x1 + 1) * (y2 - y1 + 1);
if ((x1 + y1)%2 == par) {
//top left here is white
return (((x2 - x1 + 1)*(y2 - y1 + 1) + 1)/2)*d*d;
}
else {
return (tot - ((x2 - x1 + 1)*(y2 - y1 + 1) + 1)/2)*d*d;
}
}
else if (x1 == x2 && y1 == y2) {
if ((x1 + y1)%2 == par) {
return (p.s.f - p.f.f + 1) * (p.s.s - p.f.s + 1);
}
else {
return 0;
}
}
else if (p.f.f%d == 0 && p.s.f%d == d-1 && y1 == y2) {
int tot = (x2 - x1 + 1);
if ((x1 + y1)%2 == par) {
return (tot + 1)/2 * (p.s.s - p.f.s + 1) * d;
}
else {
return (tot - (tot + 1)/2) * (p.s.s - p.f.s + 1) * d;
}
}
else if (p.f.s%d == 0 && p.s.s%d == d-1 && x1 == x2) {
int tot = (y2 - y1 + 1);
if ((x1 + y1)%2 == par) {
return (tot + 1)/2 * (p.s.f - p.f.f + 1)*d;
}
else {
return (tot - (tot + 1)/2) * (p.s.f - p.f.f + 1)*d;
}
}
else if (x1 == x2) {
auto left = rec;
left.s.s = y1*d+d-1;
auto right = rec;
right.f.s = y2*d;
rec.f.s = left.s.s+1;
rec.s.s = right.f.s-1;
return calc(left, d, par) + calc(right, d, par) + calc(rec, d, par);
}
else if (y1 == y2) {
auto top = rec;
top.s.f = x1*d + d - 1;
auto bot = rec;
bot.f.f = x2*d;
rec.f.f = top.s.f+1;
rec.s.f = bot.f.f-1;
return calc(top, d, par) + calc(bot, d, par) + calc(rec, d, par);
}
else {
auto tleft = rec;
auto bleft = rec;
auto tright = rec;
auto bright = rec;
tleft.s.s = y1*d + d-1;
tleft.s.f = x1*d + d-1;
bleft.f.f = x2*d;
bleft.s.s = y1*d + d-1;
tright.f.s = y2*d;
tright.s.f = x1*d + d-1;
bright.f.f = x2*d;
bright.f.s = y2*d;
auto left = rec;
auto right = rec;
auto bot = rec;
auto top = rec;
left.f.f = tleft.s.f+1;
left.s.f = bleft.f.f-1;
left.s.s= y1*d + d-1;
right.f.f = tright.s.f+1;
right.s.f = bright.f.f-1;
right.f.s=y2*d;
bot.f.s = bleft.s.s+1;
bot.s.s=bright.f.s-1;
bot.f.f=x2*d;
top.f.s=tleft.s.s+1;
top.s.s=tright.f.s-1;
top.s.f=x1*d+d-1;
rec.f.f = d*(x1 + 1);
rec.f.s = d*(y1 + 1);
rec.s.f = d*x2-1;
rec.s.s = d*y2-1;
return calc(tleft, d, par) + calc(bleft, d, par) + calc(tright, d, par) + calc(bright, d, par) + calc(left, d, par) + calc(right, d, par) + calc(bot, d, par) + calc(top, d, par) + calc(rec, d, par);
}
}
signed main() {
cin.tie(0);
cin.sync_with_stdio(0);
cerr << calc({{1, 5}, {8, 7}}, 3, 0) << endl;
int N, K;
cin >> N >> K;
vector<pair<pair<int, int>, pair<int, int>>> vec(K);
for (int i = 0; i < K; i++) {
cin >> vec[i].f.f >> vec[i].f.s >> vec[i].s.f >> vec[i].s.s;
vec[i].f.f--;
vec[i].f.s--;
vec[i].s.f--;
vec[i].s.s--;
}
int ans = N*N;
for (int d = 1; d < N; d++) {
if (N%d == 0) {
int cnt = N/d;
// ll white;
// ll black;
int black = d*d*((cnt * cnt)+1)/2;
int white = d*d*(cnt*cnt - ((cnt*cnt)+1)/2);
for (auto& p : vec) {
int tot = (p.s.f - p.f.f + 1) * (p.s.s - p.f.s + 1);
int res1 = calc(p, d, 0);
int res2 = calc(p, d, 1);
black += res2;
black -= tot-res2;
white += res1;
white -= tot-res1;
}
ans = min({ans, white, black});
//top left is black
}
}
cout << ans << '\n';
}
