#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define itr iterator
typedef pair<int,int> pii;
const int MAX=1e6;
const int INF=1e12;
pii arr[MAX];
int N,K,ans;
int cal(int X)
{
if(X==N)
return INF;
//At first color the cell (1,1) white
int res=(((N/X)*(N/X))/2)*X*X;
for(int A=1;A<=K;A++)
{
if((arr[A].first+arr[A].second)%2==0) //this cell should be white
res++;
else //this cell should be black
res--;
}
//Color the cell (1,1) black
int res_2=(((N/X)*(N/X))/2+(N%2))*X*X;
for(int A=1;A<=K;A++)
{
if((arr[A].first+arr[A].second)%2==0) //this cell should be black
res_2--;
else
res_2++;
}
return min(res,res_2);
}
signed main()
{
ios_base::sync_with_stdio(false);
ans=INF;
cin>>N>>K;
for(int A=1;A<=K;A++)
cin>>arr[A].first>>arr[A].second>>arr[A].first>>arr[A].second;
for(int A=1;A*A<=N;A++)
{
if(!(N%A))
{
if(A*A==N)
ans=min(ans,cal(A));
else
ans=min(ans,cal(A)),
ans=min(ans,cal(N/A));
}
}
cout<<ans;
return 0;
}
