#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,mas[1009][1009],jj,jjj,pas,zx,xc,zzx,zxc;
pair <pair <long long, long long>, pair <long long, long long> > p[100009];
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
pas=a*a;
for(i=1; i<=b; i++){
cin>>p[i].first.first>>p[i].first.second>>p[i].second.first>>p[i].second.second;
if(a<=1000){
mas[p[i].first.first][p[i].first.second]++;
}else{
if((p[i].first.first+p[i].first.second)%2==0) zx++; else xc++;
}
}
zzx=a/2*a/2;
zxc=(a/2+a%2)*(a/2+a%2);
if(a>1000){
d=xc+zxc-zx;
e=zx+zzx-xc;
cout<<min(d,e);
return 0;
}
for(i=1; i<=1002; i++){
for(j=1; j<=1002; j++) mas[i][j]+=mas[i-1][j]+mas[i][j-1]-mas[i-1][j-1];
}
for(c=1; c<a; c++){
if(a%c!=0) continue;
long long ans=0;
e=c*c;
for(i=c; i<=a; i+=c){
for(j=c; j<=a; j+=c){
d=mas[i][j]-mas[i-c][j]-mas[i][j-c]+mas[i-c][j-c];
if((i/c+j/c)%2==0) ans+=d; else ans+=e-d;
}
}
/* if(ans==11){
cout<<c<<" 1"<<endl;
}*/
if(pas>ans) pas=ans;
ans=0;
for(i=c; i<=a; i+=c){
for(j=c; j<=a; j+=c){
d=mas[i][j]-mas[i-c][j]-mas[i][j-c]+mas[i-c][j-c];
if((i/c+j/c)%2==1) ans+=d; else ans+=e-d;
}
}
/* if(ans==11){
cout<<c<<" 2"<<endl;
}*/
if(pas>ans) pas=ans;
}
cout<<pas;
return 0;
}
