#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct eventhelp{
int t;
int l, r;
int val;
int type;
};
void add_int(int l, int r, long long val, long long &cnti, long long &cntp){
int pare, impare;
int dst = r - l + 1;
pare = dst/2;
impare = dst/2;
if(dst%2 == 1){
if(l%2 == 0)
pare++;
else
impare++;
}
cnti += 1LL * impare * val;
cntp += 1LL * pare * val;
}
vector<eventhelp> ev;
long long ans = LLONG_MAX;
int n;
bool cmpev(eventhelp a, eventhelp b){
if(a.t == b.t)
return a.type > b.type;
return a.t < b.t;
}
long long imp[N], pr[N];
void solve(int len){
vector<eventhelp> evc = ev;
for(int i=len; i<=n;i+=len){
evc.push_back({i, 0, 0, 0});
}
inplace_merge(evc.begin(), evc.begin() + ev.size(), evc.end(), cmpev);
long long sumi = 0, acti = 0, sump = 0, actp = 0;
for(auto e:evc){
if(e.type != 0){
int fgroup = (e.l - 1)/len + 1;
int lgroup = (e.r - 1)/len + 1;
if(fgroup + 1 <= lgroup - 1){
add_int(fgroup, lgroup, 1LL* e.val * len, sumi, sump);
add_int(fgroup, lgroup, 1LL* e.type * len, acti, actp);
}
if(fgroup != lgroup){
add_int(fgroup, fgroup, 1LL * e.val * (fgroup*len - e.l + 1), sumi, sump);
add_int(fgroup, fgroup, 1LL * e.type * (fgroup*len - e.l + 1), acti, actp);
add_int(lgroup, lgroup, 1LL * e.val * (e.r - (lgroup - 1)*len), sumi, sump);
add_int(lgroup, lgroup, 1LL * e.type * (e.r - (lgroup - 1)*len), acti, actp);
}
if(fgroup == lgroup){
add_int(fgroup, fgroup, 1LL * e.val * (e.r - e.l + 1), sumi, sump);
add_int(fgroup, fgroup, 1LL * e.type * (e.r - e.l + 1), acti, actp);
}
}
else{
long long csumi, csump;
csumi = sumi - acti * (n - e.t);
csump = sump - actp * (n - e.t);
imp[e.t/len] = csumi;
pr[e.t/len] =csump;
}
}
long long fans = 0, sans = 0;
for(int i = 1; i<=n/len;i++){
long long ci, cp;
ci = imp[i] - imp[i-1];
cp = pr[i] - pr[i -1];
int nrp = (n/len)/2, nri = n/len - nrp;
if(i %2 == 1){
fans += 1LL*len*len*nri - ci + cp;
sans += 1LL*len*len*nrp - cp + ci;
}
else{
sans += 1LL*len*len*nri - ci + cp;
fans += 1LL*len*len*nrp - cp + ci;
}
}
ans = min(ans, sans);
ans = min(ans, fans);
}
int main()
{
//freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int k;
cin>>n>>k;
for(int i=1;i<=k;i++){
int x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
ev.push_back({x1, y1, y2, n - x1 + 1, 1});
ev.push_back({x2, y1, y2,-(n - x2), -1});
}
sort(ev.begin(), ev.end(), cmpev);
for(int d = 1; d<n; d++){
if(n%d == 0)
solve(d);
}
cout<<ans;
return 0;
}
