#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
bool get_color(pair<ll, ll> p, ll d) {
return (p.first / d + p.second / d) & 1;
}
ll intersect(pair<pair<ll, ll>, pair<ll, ll>> r1, pair<pair<ll, ll>, pair<ll, ll>> r2) {
ll w = min(r1.second.first, r2.second.first) - max(r1.first.first, r2.first.first);
ll h = min(r1.second.second, r2.second.second) - max(r1.first.second, r2.first.second);
//cout << w << ' ' << h << endl;
if (w < 0 || h < 0)
return 0;
return w * h;
}
signed main() {
ll n, k;
cin >> n >> k;
vector<pair<pair<ll, ll>, pair<ll, ll>>> rect(k);
for (ll i = 0; i < k; ++i) {
cin >> rect[i].first.first >> rect[i].first.second >> rect[i].second.first >> rect[i].second.second;
--rect[i].first.first, --rect[i].first.second, --rect[i].second.first, --rect[i].second.second;
}
vector<ll> divs;
for (ll p = 1; p < n; ++p) {
if (n % p == 0)
divs.push_back(p);
}
ll szd = divs.size();
vector<ll> ans(szd);
for (ll di = 0; di < szd; ++di) {
ll d = divs[di];
if (n / d == 0)
ans[di] = n * n / 2;
else
ans[di] = d * d * ((n / d) * (n / d) / 2);
}
for (auto [ld, ru] : rect) {
for (ll di = 0; di < szd; ++di) {
ll d = divs[di];
ll r = ld.first + (ru.first - ld.first) % (2 * d);
ll u = ld.second + (ru.second - ld.second) % (2 * d);
pair<pair<ll, ll>, pair<ll, ll>> rct = {ld, {r + 1, u + 1}};
ll bi = ld.first / (2 * d) * (2 * d);
ll bj = ld.second / (2 * d) * (2 * d);
for (ll i = 0; i < 4; ++i) for (ll j = 0; j < 4; ++j) {
ll val = intersect(rct, {{bi + d * i, bj + d * j}, {bi + d * i + d, bj + d * j + d}});
if ((i + j) % 2)
ans[di] -= val;
else
ans[di] += val;
}
//ans[di] += intersect(rct, {{bi, bj}, {bi + d, bj + d}});
//ans[di] -= intersect(rct, {{bi + d, bj}, {bi + 2 * d, bj + d}});
//ans[di] -= intersect(rct, {{bi, bj + d}, {bi + d, bj + 2 * d}});
//ans[di] += intersect(rct, {{bi + d, bj + d}, {bi + 2 * d, bj + 2 * d}});
}
}
ll mnans = n * n;
for (auto x : ans) {
mnans = min({mnans, x, n * n - x});
}
cout << mnans << '\n';
}
