#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
const ll INF = 2e18;
const ll MOD = 1e9+7;
struct segtree{
struct node{
ll on, off, upd;
};
vector<node> t;
ll sz, rsz;
void init(ll N){
rsz=N; sz=N*4;
t.resize(sz);
gen(0, rsz-1, 1);
}
void gen(ll tl, ll tr, ll v){
if (tl==tr){
t[v] = {0, 1, 0};
}else{
ll tm = (tl+tr)/2;
gen(tl, tm, v*2);
gen(tm+1, tr, v*2+1);
t[v].on=t[v].upd=0;
t[v].off=t[v*2].off+t[v*2+1].off;
}
}
void preprocess(ll tl, ll tr, ll v){
if (tl!=tr) {
t[v*2].upd+=t[v].upd; t[v*2+1].upd+=t[v].upd;
}
if (t[v].upd%2){
swap(t[v].off, t[v].on);
}
t[v].upd=0;
}
void flip(ll tl, ll tr, ll v, ll l, ll r){
preprocess(tl, tr, v);
if (tl==l and tr==r){
t[v].upd++;
preprocess(tl, tr, v);
}else if (l>r) return;
else{
ll tm = (tl+tr)/2;
flip(tl, tm, v*2, l, min(r, tm));
flip(tm+1, tr, v*2+1, max(l, tm+1), r);
t[v].on=t[v*2].on+t[v*2+1].on;
t[v].off=t[v*2].off+t[v*2+1].off;
}
}
void flip(ll l, ll r){
flip(0, rsz-1, 1, l, r);
}
} tr;
ll n, k;
vector<vector<pair<ll, ll>>> upd;
ll check(ll x){
tr.init(n);
for (ll i=0; i<n; i++){
if ((i/x)%2) tr.flip(i, i);
}
ll res=0;
for (ll i=0; i<n; i++){
if (i%x==0) tr.flip(0, n-1);
for (auto ch:upd[i]){
tr.flip(ch.ff, ch.ss);
}
res+=tr.t[1].on;
}
tr.init(n);
for (ll i=0; i<n; i++){
if ((i/x)%2==0) tr.flip(i, i);
}
ll res2=0;
for (ll i=0; i<n; i++){
if (i%x==0) tr.flip(0, n-1);
for (auto ch:upd[i]){
tr.flip(ch.ff, ch.ss);
}
res2+=tr.t[1].on;
}
// cout << x << ": " << res << " - " << res2 << ln;
return min(res, res2);
}
void solve(){
cin >> n >> k;
upd.resize(n+1);
for (ll i=0; i<k; i++){
ll si, sj, ti, tj; cin >> si >> sj >> ti >> tj;
si--; sj--; ti--; tj--;
upd[sj].push_back({si, ti});
upd[tj+1].push_back({si, ti});
}
ll res=INF;
for (ll i=1; i*i<=n; i++){
if (n%i==0){
res=min(res, check(i));
if (n/i<n) res=min(res, check(n/i));
}
}
cout << res << ln;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto start = chrono::high_resolution_clock::now();
ll t=1;
// cin >> t;
while (t--) solve();
#ifdef LOCAL
auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
#endif
}
