//#pragma GCC optimize("O3,unroll-loops,inline,fast-math")
//#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2,fma,bmi2,abm,popcnt,mmx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(a) a.begin(), a.end()
void solve() {
int n, k;
cin >> n >> k;
vector<array<int, 4>> p(k);
for (auto &i : p)
cin >> i[0] >> i[1] >> i[2] >> i[3];
int res = 1e18;
auto pref = [](int i, int j, int l) {
int ii = i / l * l, jj = j / l * l;
int res = 0;
if ((ii / l + jj / l) % 2) {
res += (ii / l) * (jj / l) / 2 * l * l;
res += ((jj / l) + 1) / 2 * l * (i - ii);
res += ((ii / l) + 1) / 2 * l * (j - jj);
} else {
res += (i - ii) * (j - jj);
res += ((ii / l) * (jj / l) + 1) / 2 * l * l;
res += (jj / l) / 2 * l * (i - ii);
res += (ii / l) / 2 * l * (j - jj);
}
return res;
};
auto upd = [&](int l) {
int now = n * n - pref(n, n, l);
for (auto i : p) {
int w = pref(i[2], i[3], l) + pref(i[0] - 1, i[1] - 1, l) - pref(i[2], i[1] - 1, l) - pref(i[0] - 1, i[3], l);
now += w;
now -= (i[2] - i[0] + 1) * (i[3] - i[1] + 1) - w;
}
res = min(res, min(now, n * n - now));
};
for (int i = 1; i * i <= n; ++i)
if (n % i == 0) {
upd(i);
if (n / i != i && i != 1)
upd(n / i);
}
cout << res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--)
solve();
}
