#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define OK puts("OK");
#define fr first
#define sc second
#define ret return
#define scan1(a) scanf("%lld",&a);
#define scan2(a,b) scanf("%lld %lld",&a, &b);
#define scan3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define pb push_back
#define endi puts("");
const int N = 1e5+12,INF=1e9+7;
int q[2501][2501],dp[2501][2501],resh[N],ans[N],n;
int sum(int x1,int y1,int x2,int y2){
ret dp[x2][y2]+dp[x1][y1]-dp[x1][y2]-dp[x2][y1];
}
int fun(int x){
int i,j,ans=0,res=0,c=1;
for (i=0;i<n;i+=x){
if (c%2)
for (j=0;j<n;j+=x*2){
res += x*x-sum(i,j,i+x,j+x);
}
else {
for (j=x;j<n;j+=x*2){
res += x*x-sum(i,j,i+x,j+x);
}
}
c++;
}
c=0;
for (i=0;i<n;i+=x){
if (c%2)
for (j=0;j<n;j+=x*2){
res += sum(i,j,i+x,j+x);
}
else {
for (j=x;j<n;j+=x*2){
res += sum(i,j,i+x,j+x);
}
}
c++;
}
ret (res);
}
int fun1(int x){
int i,j,ans=0,res=0,c=0;
for (i=0;i<n;i+=x){
if (c%2)
for (j=0;j<n;j+=x*2){
res += x*x-sum(i,j,i+x,j+x);
}
else {
for (j=x;j<n;j+=x*2){
res += x*x-sum(i,j,i+x,j+x);
}
}
c++;
}
c=1;
for (i=0;i<n;i+=x){
if (c%2)
for (j=0;j<n;j+=x*2){
res += sum(i,j,i+x,j+x);
}
else {
for (j=x;j<n;j+=x*2){
res += sum(i,j,i+x,j+x);
}
}
c++;
}
ret (res);
}
main(){
int k,i,j;
vector <int> v;
scan2(n,k)
while (k--){
int x1,x2,y1,y2;
scan2(x1,y1)
scan2(x2,y2)
q[x1][y1]++;
q[x2+1][y2+1]++;
q[x1][y2+1]--;
q[x2+1][y1]--;
}
for (i=1;i<=n;++i){
for (j=1;j<=n;++j){
q[i][j]+=q[i-1][j]+q[i][j-1]-q[i-1][j-1];
}
}
for (i=1;i<=n;++i){
for (j=1;j<=n;++j){
dp[i][j] = dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+q[i][j];
}
}
for (i=2;i*i<=n;++i){
if (n%i==0){
v.pb(i);
if (i*i != n)v.pb(n/i);
}
}
int ans=min(fun(1),fun1(1));
for (i=0;i<v.size();++i){
ans = min(ans,min(fun(v[i]),fun1(v[i])));
}
cout <<ans;
}
