#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int n,k,odd,even;
int64_t res=1e12;
vector<ii> g1[100005],g2[100005];
int Cal(int u,int v,int block)
{
return ((u-1)/block+1+(v-1)/block+1)%2;
}
void Update(int i,int l,int r,int block,int val)
{
int ll=(l-1)/block+2;
int rr=(r-1)/block;
if(ll==rr+2)
{
if(Cal(i,l,block)==1)
odd+=(r-l+1)*val;
else
even+=(r-l+1)*val;
return;
}
odd+=(rr-ll+1)/2*block*val;
even+=(rr-ll+1)/2*block*val;
if((rr-ll+1)%2==1)
{
if(Cal(i,(ll-1)*block+1,block)==1)
odd+=block*val;
else
even+=block*val;
}
if(Cal(i,l,block)==1)
odd+=((ll-1)*block-l+1)*val;
else
even+=((ll-1)*block-l+1)*val;
if(Cal(i,r,block)==1)
odd+=(r-(rr*block))*val;
else
even+=(r-(rr*block))*val;
}
void Check(int block)
{
int64_t sodd=0,seven=0,tmp=n/block,codd,ceven;
if(tmp%2==0)
codd=ceven=int64_t(n)*int64_t(n)/int64_t(2);
else
{
ceven=(int64_t(n)*int64_t(n)+int64_t(block)*int64_t(block))/int64_t(2);
codd=int64_t(n)*int64_t(n)-ceven;
}
odd=even=0;
for(int i=1;i<=n;i++)
{
if(i>1&&(i-1)/block+1!=(i-2)/block+1)
swap(odd,even);
for(int j=0;j<g1[i].size();j++)
Update(i,g1[i][j].first,g1[i][j].second,block,1);
sodd+=odd;
seven+=even;
for(int j=0;j<g2[i].size();j++)
Update(i,g2[i][j].first,g2[i][j].second,block,-1);
}
res=min(res,min(codd-sodd+seven,ceven-seven+sodd));
}
int main()
{
ios_base::sync_with_stdio(false);
//freopen("TEST.INP","r",stdin);
//freopen("TEST.OUT","w",stdout);
cin>>n>>k;
int u1,v1,u2,v2;
while(k--)
{
cin>>u1>>v1>>u2>>v2;
g1[u1].push_back(ii(v1,v2));
g2[u2].push_back(ii(v1,v2));
}
for(int i=1;i<n;i++)
if(n%i==0)
Check(i);
cout<<res;
}
