#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 100000000000000000
typedef long long ll;
using namespace std;
struct point{
ll x1,y1,x2,y2;
};
point p[100001];
ll n,k;
ll solve(ll x,ll y,ll sz){
if(x==n+1 || y==n+1) return (ll)0;
ll black=0;
ll xx=((x+sz-1)/sz)*sz;
ll yy=((y+sz-1)/sz)*sz;
// cout << xx << ' ' << yy << '\n';
ll a=(n-xx)/sz;
ll b=(n-yy)/sz;
black+=(((a*b+1)/2)*sz*sz);
ll c=xx-x+1;
ll d=yy-y+1;
ll aa,bb;
if(a%2) bb=b/2;
else bb=(b+1)/2;
if(b%2) aa=a/2;
else aa=(a+1)/2;
black+=(bb*c*sz);
black+=(aa*d*sz);
if((xx/sz+yy/sz)%2==0) black+=(c*d);
return black;
}
int main(){
//ios_base::sync_with_stdio(NULL);
// cin.tie(NULL);
// cout.tie(NULL);
cin >> n >> k;
for(ll i=1;i<=k;i++){
cin >> p[i].x1 >> p[i].y1 >> p[i].x2 >> p[i].y2;
}
ll ans=INF;
// cout << solve(4,1,) << '\n';
for(ll i=1;i<n;i++){
if(n%i==0){
ll black=0,white=0;
for(ll j=1;j<=k;j++){
ll z=(solve(p[j].x1,p[j].y1,i)-solve(p[j].x1,p[j].y2+1,i)-solve(p[j].x2+1,p[j].y1,i)+solve(p[j].x2+1,p[j].y2+1,i));
black+=(z);
white+=((p[j].x2+1-p[j].x1)*(p[j].y2+1-p[j].y1)-z);
// if(i==2) cout << white << '\n';
}
// cout << black << ' ' << white << '\n';
if((n/i)%2){
ans=min(ans,((n*n+i*i)/2-black+white));
ans=min(ans,((n*n-i*i)/2-white+black));
}
else ans=min(ans,n*n/2-abs(black-white));
}
}
cout << ans;
}
