#include <vector>
#include <iostream>
#include <climits>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define MN 100071
using ll = long long;
using namespace std;
int n, k;
namespace AINT {
int V[3 * MN];
void clear(const int &u = 1, const int &s = 1, const int &d = n) {
V[u] = 0;
if(s != d)
clear(u * 2, s, (s + d) /2), clear(u * 2 + 1, (s + d) / 2 + 1, d);
}
static inline void prp(const int &u, const int &s, const int &d) {
if(!(V[u] & (1 << 30))) return;
V[u] = (d - s + 1 - (V[u] ^ (1 << 30)));
if(s != d)
V[u * 2] ^= 1 << 30, V[u * 2 + 1] ^= 1 << 30;
}
void update(const int &l, const 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) {
V[u] ^= 1 << 30;
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] & 1073741823) + (V[u * 2 + 1] & 1073741823);
}
}
vector<pair<int, int>> OP[MN];
ll acopera(int l) {
if(l == n) return LLONG_MAX;
///c0 = 1 daca coloram primul patrat
AINT::clear();
for(int i = 1 + 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] & 1073741823;
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{1};
for (int i = 2; 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) {
ll v = acopera(it);
re = min(re, min(v, 1ll * n * n - v));
}
cout << re << "\n";
return 0;
}
