//Just try and the idea will come
#include<bits/stdc++.h>
#define int long long int
#define fr first
#define sc second
using namespace std;
int n,k,i,j,x,y,res;
pair<int,int>p1[100001],p2[100001];
int get_x(int k,int x,int white){
int res;
if(white)res=((x/k+1)/2)*k;
else res=((x/k)/2)*k;
if(((x+k-1)/k)%2==white)res+=(x%k);
return res;
}
int get_xy(int k,int y,int x){
if(x==0||y==0)return 0;
int res=(((x/k)*(y/k)+1)/2)*k*k,a,b;
a=(x+k-1)/k;b=(y+k-1)/k;
res+=(x%k)*get_x(k,y,a%2);
res+=(y%k)*get_x(k,x,b%2);
if(!((a+b)&1))res-=(x%k)*(y%k);
return res;
}
int get_range(int k,int x,int y,int x2,int y2){
return get_xy(k,x2,y2)+get_xy(k,x-1,y-1)-get_xy(k,x-1,y2)-get_xy(k,x2,y-1);
}
int get(int f){
int cnt=0,c[2],a,b;
c[0]=c[1]=0;
for(int i=0;i<k;i++){
//c[(p[i].fr/f+p[i].sc/f)%2]++;
a=(p1[i].second-p2[i].second+1)*(p1[i].first-p2[i].first+1);
b=get_range(k,p1[i].first,p1[i].second,p2[i].first,p2[i].second);
c[0]+=b;
c[1]+=a-b;
}
int m=n/f;
int res=f*f*((m/2)*m+((m%2)*(m/2)))-c[1]+c[0];
res=min(res,f*f*((m/2)*m+((m%2)*((m+1)/2)))-c[0]+c[1]);
return res;
}
main(){
scanf("%lld%lld",&n,&k);
for(i=0;i<k;i++){
scanf("%lld%lld%lld%lld",&p1[i].fr,&p1[i].sc,&p2[i].fr,&p2[i].sc);
}
res=get(1);
for(j=2;j*j<=n;j++){
if(n%j==0){
res=min(res,get(j));
res=min(res,get(n/j));
}
}
printf("%lld",res);
}
/*
int get_x(int k,int x,int white){
int res;
if(white)res=((x/k+1)/2)*k;
else res=((x/k)/2)*k;
if(((x+k-1)/k)%2==white)res+=(x%k);
return res;
}
int get_xy(int k,int y,int x){
int res=(((x/k)*(y/k)+1)/2)*k*k,a,b;
a=(x+k-1)/k;b=(y+k-1)/k;
res+=(x%k)*get_x(k,y,a%2);
res+=(y%k)*get_x(k,x,b%2);
if(!((a+b)&1))res-=(x%k)*(y%k);
return res;
}
*/
