#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const ll N=1000006, INF=1e18;
ll e, t, n, m, a[N], i, j, k, u, x1, x2, X1, X2, ans[N], xl[N], yl[N], xr[N], yr[N], Ans, sz, w, r, X, Y, xx, yy, xxx, yyy, A, B;
vector <int> v;
ll calc(ll x, ll y){
if(!x||!y) return 0;
t=0;
X=x/e*e;
Y=y/e*e;
xx=X/e;
yy=Y/e;
t+=(((xx*yy+1)/2)*e*e);
xxx=x-X;
yyy=y-Y;
if(xx&1) B=(yy>>1);
else B=(yy+1>>1);
if(yy&1) A=(xx>>1);
else A=(xx+1>>1);
t+=(B*xxx*e);
t+=(A*yyy*e);
if(!((X/e+Y/e)&1)) t+=(xxx*yyy);
// cout<<x<<" "<<y<<" "<<t<<endl;
return t;
}
int main(){ios_base::sync_with_stdio(false), cin.tie(0);
long long ee;
cin>>n>>m;
Ans=INF;
for (int i=1; i<=m; i++)
cin>>xl[i]>>yl[i]>>xr[i]>>yr[i],
a[i]=(xr[i]-xl[i]+1)*(yr[i]-yl[i]+1);
for (int i=1; i<n; i++)
if(n%i==0)
v.pb(i);
k=v.size();
for(int i=0; i<k; i++){
e=v[i];
ans[i]=(n*n/e/e+1)/2*e*e;//cout<<ans[i]<<" ";
for (int j=1; j<=m; j++)
ans[i]+=a[j],
ans[i]-=2*(calc(xr[j], yr[j])-(calc(xl[j]-1, yr[j])+calc(xr[j], yl[j]-1)-calc(xl[j]-1, yl[j]-1)));
Ans=min(Ans, min(ans[i], n*n-ans[i]));//cout<<ans[i]<<endl;
}
cout<<Ans;
}
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
4 1
4 1 4 4
*/
