#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;
#define int ll
ll n,m;
ll ans=0;
pair<pair<int,int>,pair<int,int>>arr[100023];
ll cal(int k,int a,int b,int h){
int res=0;
if(b/k==a/k){
res=b-a+1;
}
else if(((a/k)&1)==((b/k)&1)){
res=(b-(b%k)-(a+k-(a%k))-k)/(k*2)+(k-(a%k))+(b%k)+1;
}
else{
res=(b-(b%k)-(a+k-(a%k)))/(k*2)+(k-(a%k));
}
if(((a/k)&1)==((h/k)&1))res=b-a+1-res;
return res-(b-a+1-res);
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>n>>m;
ans=n*n;
for(int i=1;i<=m;i++){
cin>>arr[i].fr.fr>>arr[i].fr.sc>>arr[i].sc.fr>>arr[i].sc.sc;
arr[i].fr.fr--;
arr[i].fr.sc--;
arr[i].sc.fr--;
arr[i].sc.sc--;
}
for(int i=1;i*i<=n;i++){
if(i*(n/i)==n){
ll sum=0;
for(int j=1;j<=m;j++){
sum+=cal(i,arr[j].fr.fr,arr[j].sc.fr,arr[j].fr.sc)*(((((arr[j].fr.fr/i)&1)==((arr[j].fr.sc/i)&1))?1:-1)*cal(i,arr[j].fr.sc,arr[j].sc.sc,arr[j].fr.fr));
}
ans=min(ans,min((((n/i)&1)?(n*n-i*i)/2:(n*n)/2)+sum,(((n/i)&1)?(n*n+i*i)/2:(n*n)/2)-sum));
if(i==1)continue;
i=n/i;
sum=0;
for(int j=1;j<=m;j++){
sum+=cal(i,arr[j].fr.fr,arr[j].sc.fr,arr[j].fr.sc)*(((((arr[j].fr.fr/i)&1)==((arr[j].fr.sc/i)&1))?1:-1)*cal(i,arr[j].fr.sc,arr[j].sc.sc,arr[j].fr.fr));
}
ans=min(ans,min((((n/i)&1)?(n*n-i*i)/2:(n*n)/2)+sum,(((n/i)&1)?(n*n+i*i)/2:(n*n)/2)-sum));
i=n/i;
}
}
cout<<ans;
}
