#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int MAX = 1e5 + 5;
const ll oo = 1e15;
int tree[MAX * 4], lazy[MAX * 4];
void build(int node, int l, int r, int k){
lazy[node] = 0;
if(l == r){
tree[node] = ((l - 1) / k) & 1;
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid, k);
build(node * 2 + 1, mid + 1, r, k);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void relax(int node, int l, int r){
if(!lazy[node]) return;
tree[node] = (r - l + 1) - tree[node];
if(l != r){
lazy[node * 2] ^= 1;
lazy[node * 2 + 1] ^= 1;
}
lazy[node] = 0;
return;
}
void update(int node, int l, int r, int ql, int qr){
relax(node, l, r);
if(ql > r || qr < l) return;
if(ql <= l && r <= qr){
lazy[node] ^= 1;
relax(node, l, r);
return;
}
int mid = (l + r) / 2;
update(node * 2, l, mid, ql, qr);
update(node * 2 + 1, mid + 1, r, ql, qr);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
vector<array<int, 2>> events[MAX];
int n, k;
ll check(int d){
build(1, 1, n, d);
ll a = 0, b = 0;
for (int i = 1; i <= n; i++)
{
if((i - 1) % d == 0) lazy[1] ^= 1;
for(auto& e:events[i]){
update(1, 1, n, e[0], e[1]);
}
relax(1, 1, n);
a += tree[1];
b += n - tree[1];
}
return min(a, b);
}
void solve(){
cin >> n >> k;
for (int i = 0; i < k; i++)
{
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
events[x1].push_back({y1, y2});
events[x2 + 1].push_back({y1, y2});
}
ll ans = oo;
for (int i = 1; i * i <= n; i++)
{
if(n % i == 0){
ans = min(ans, check(i));
if(i != 1){
ans = min(ans, check(n / i));
}
}
}
cout << ans << '\n';
}
int main()
{
solve();
}
