#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e18;
struct Fenwick {
vector<int> tree;
int n;
void init(int len) {
n = len;
tree.assign(n + 1, 0);
}
void update(int i, int v) {
i++;
while (i <= n) {
tree[i] += v;
i += i & (-i);
}
}
int get(int i) {
i++;
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= i & (-i);
}
return sum;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
};
void solve() {
int n, k;
cin >> n >> k;
vector<vector<pair<int, int>>> in(n + 1), out(n + 1);
for (int i = 0; i < k; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
in[x1].emplace_back(y1, y2);
out[x2].emplace_back(y1, y2);
}
vector<int> del;
for (int i = 1; i * i <= n; i++) {
if (n % i) continue;
del.emplace_back(i);
if (i != 1 and i * i != n) del.emplace_back(n / i);
}
ll ans = 1e18;
for (int p: del) {
vector<int> b, w;
for (int i = 1; i <= n; i++) {
if ((i - 1) / p % 2) w.emplace_back(i);
else b.emplace_back(i);
}
for (int s = 0; s < 2; s++) {
ll need = 0;
int bib = 0, biw = 0;
for (int i = 1; i <= n; i++) {
for (auto [l, r]: in[i]) {
bib += upper_bound(b.begin(), b.end(), r) - lower_bound(b.begin(), b.end(), l);
biw += upper_bound(w.begin(), w.end(), r) - lower_bound(w.begin(), w.end(), l);
}
int wib = (int) b.size() - bib;
int wiw = (int) w.size() - biw;
bool wh = true;
if ((i - 1) / p % 2 == 0) wh = !wh;
if (s) wh = !wh;
need += wh ? biw + wib : bib + wiw;
for (auto [l, r]: out[i]) {
bib -= upper_bound(b.begin(), b.end(), r) - lower_bound(b.begin(), b.end(), l);
biw -= upper_bound(w.begin(), w.end(), r) - lower_bound(w.begin(), w.end(), l);
}
}
// cout << p << ' ' << s << ' ' << need << endl;
ans = min(ans, need);
}
}
cout << ans;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int queries = 1;
// cin >> queries;
for (int test_case = 1; test_case <= queries; test_case++) {
#ifdef sunnatov
cout << "Test case: " << test_case << endl;
#endif
solve();
cout << '\n';
}
}
