#include <bits/stdc++.h>
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll long long
#define ld long double
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const int N = 1e5 + 2;
int n, sum[100002], k, lazy[400002], aint[400002], l[400002], r[400002];
struct query {
int type, l, r;
bool operator < (const query &other) {
return type < other.type;
}
};
vector<query>q[100002];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
while (k--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--; y1--; x2--; y2--;
q[x1].push_back({1, y1, y2});
q[x2 + 1].push_back({0, y1, y2});
}
for (int i = 0; i < n; i++)
sort(q[i].begin(), q[i].end());
ll sol = 1ll * n * n, div = 0;;
for (int lat = 1; lat < n; lat++) {
if (n % lat == 0) {
div++;
for (int i = 0; i < n; i++) {
sum[i] = ((i / lat) & 1) + (i > 0 ? sum[i - 1] : 0);
}
ll lin = sum[n - 1], nr = 0;
for (int i = 0; i < n; i++) {
for (auto it : q[i]) {
if (it.type == 0) {
lin = lin - (it.r - it.l + 1) + 2 * (sum[it.r] - (it.l > 0 ? sum[it.l - 1] : 0));
}
else {
lin = lin + (it.r - it.l + 1) - 2 * (sum[it.r] - (it.l > 0 ? sum[it.l - 1] : 0));
}
}
if ((i / lat) & 1)
nr += n - lin;
else
nr += lin;
}
sol = min(sol, min(nr, 1l * n * n - nr));
}
}
cout << sol;
return 0;
}
