#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
ll n,k,p,u,ans,color[100005],i,j,qanak[105],v,x[100005],y[100005],p1,p2,q1,q2,ans1,ans2;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(i=2;i<=100000;i++)
{
if(!color[i])
{
for(j=2*i;j<=100000;j+=i)
color[j]=1;
}
}
cin>>n>>k;
if(color[n]==0)
{
for(i=1;i<=k;i++)
{
cin>>x[i]>>y[i]>>x[i]>>y[i];
if(x[i]%2==y[i]%2)
u++;
else
v++;
}
p=n*n/2+1-u+v;
ans=n*n/2-v+u;
cout<<min(ans,p)<<endl;
return 0;
}
for(i=n;i>=2;i--)
{
if(!color[i] && n%i==0)
{
p2=i;
break;
}
}
for(i=2;i<=n;i++)
{
if(!color[i] && n%i==0)
{
p1=i;
break;
}
}
for(i=1;i<=k;i++)
cin>>x[i]>>y[i]>>x[i]>>y[i];
for(i=1;i<=k;i++)
{
ll g,h;
if(x[i]%p1==0)
g=x[i]/p1;
else
g=x[i]/p1+1;
if(y[i]%p1==0)
h=y[i]/p1;
else
h=y[i]/p1+1;
if(h%2==g%2)
u++;
else
v++;
}
q1=n/p1;
if(q1%2==1)
ans1=p1*p1/2+1;
else
ans1=p1*p1/2;
ans1=ans1*q1*q1;
ans1=ans1-u+v;
ans2=p1*p1/2;
ans2=ans2*q1*q1;
ans2=ans2-v+u;
ans=min(ans1,ans2);
u=0; v=0;
for(i=1;i<=k;i++)
{
ll g,h;
if(x[i]%p2==0)
g=x[i]/p2;
else
g=x[i]/p2+1;
if(y[i]%p2==0)
h=y[i]/p2;
else
h=y[i]/p2+1;
if(h%2==g%2)
u++;
else
v++;
}
q2=n/p2;
if(q2%2==1)
ans1=p2*p2/2+1;
else
ans1=p2*p2/2;
ans1=ans1*q2*q2;
ans1=ans1-u+v;
ans2=p2*p2/2;
ans2=ans2*q2*q2;
ans2=ans2-v+u;
ans=min(ans,ans1);
ans=min(ans,ans2);
cout<<ans<<endl;
return 0;
}
