#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define MN 107171
using ll = long long;
using namespace std;
int n, k;
namespace AINT {
int V[4 * MN];
bool LZ[4 * MN];
void clear(int u = 1, int s = 1, int d = n) {
V[u] = LZ[u] = 0;
if(s != d)
clear(u * 2, s, (s + d) /2), clear(u * 2 + 1, (s + d) / 2 + 1, d);
}
void prp(int u, int s, int d) {
if(!LZ[u]) return;
V[u] = d - s + 1 - V[u];
LZ[u] = 0;
if(s != d)
LZ[u * 2] ^= 1, LZ[u * 2 + 1] ^= 1;
}
void update(int l, int r, int u = 1, int s = 1, int d = n) {
prp(u, s, d);
if(r < s || d < l) return;
if(l <= s && d <= r) {
LZ[u] ^= 1;
prp(u, s, d);
return;
}
update(l, r, u * 2, s, (s + d) / 2);
update(l, r, u * 2 + 1, (s + d) / 2 + 1, d);
V[u] = V[u * 2] + V[u * 2 + 1];
}
}
vector<pair<int, int>> OP[MN];
ll acopera(int l, int c0) {
if(l == n) return LLONG_MAX;
///c0 = 1 daca coloram primul patrat
AINT::clear();
for(int i = 1 + (1 - c0) * l; i <= n; i += 2 * l)
AINT::update(i, i + l - 1);
ll re = 0;
for(int i = 1; i <= n; ++i) {
for(auto [l, r] : OP[i])
AINT::update(l, r);
re += AINT::V[1];
if(i % l == 0)
AINT::update(1, n);
}
return re;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
cin >> n >> k;
ll re = LLONG_MAX;
for (int i = 1, a, b, c, d; i <= k; ++i) {
cin >> a >> b >> c >> d;
OP[a].emplace_back(b, d);
OP[c + 1].emplace_back(b, d);
}
vector<int> D;
for (int i = 1; i * i <= n; ++i)
if (i * i == n) D.push_back(i);
else if (n % i == 0)
D.push_back(i), D.push_back(n / i);
for (auto it: D)
re = min(re, min(acopera(it, 0), acopera(it, 1)));
cout << re << "\n";
return 0;
}
