#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define int long long
struct rect{
int x1, y1, x2, y2;
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
rect a[k];
for(int i=0; i< k; i++){
cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
a[i].x1--;
a[i].x2--;
a[i].y1--;
a[i].y2--;
}
int ans=1e12;
for(int d=1; d<n; d++){
if(n%d!=0)continue;
int flip=d*d*(((n*n)/(d*d)+1)/2);
for(int i=0; i< k; i++){
int subx1=a[i].x1/d;
int subx2=a[i].x2/d;
int suby1=a[i].y1/d;
int suby2=a[i].y2/d;
if(subx1==subx2 && suby1==suby2){
if((subx1&1)==(suby1&1))flip-=(a[i].x2-a[i].x1+1)*(a[i].y2-a[i].y1+1);
else flip+=(a[i].x2-a[i].x1+1)*(a[i].y2-a[i].y1+1);
}
else if(suby1==suby2){
int fali=(subx1+1)*d-1;
int fali2=subx2*d;
if((subx1&1)==(suby1&1))flip-=(a[i].y2-a[i].y1+1)*(fali-a[i].x1+1);
else flip+=(a[i].y2-a[i].y1+1)*(fali-a[i].x1+1);
if((subx2&1)==(suby1&1))flip-=(a[i].y2-a[i].y1+1)*(a[i].x2-fali2+1);
else flip+=(a[i].y2-a[i].y1+1)*(a[i].x2-fali2+1);
int dif=subx2-subx1-1;
if(dif%2==0)continue;
if((subx1&1)==(suby1&1))flip+=(a[i].y2-a[i].y1+1)*d;
else flip-=(a[i].y2-a[i].y1+1)*d;
}
else if(subx1==subx2){
int fali=(suby1+1)*d-1;
int fali2=suby2*d;
if((suby1&1)==(subx1&1))flip-=(a[i].x2-a[i].x1+1)*(fali-a[i].y1+1);
else flip+=(a[i].x2-a[i].x1+1)*(fali-a[i].y1+1);
if((suby2&1)==(subx1&1))flip-=(a[i].x2-a[i].x1+1)*(a[i].y2-fali2+1);
else flip+=(a[i].x2-a[i].x1+1)*(a[i].y2-fali2+1);
int dif=suby2-suby1-1;
if(dif%2==0)continue;
if((suby1&1)==(subx1&1))flip+=(a[i].x2-a[i].x1+1)*d;
else flip-=(a[i].x2-a[i].x1+1)*d;
}
else{
if(subx1%2==suby1%2)flip-=(subx1*d-a[i].x1)*(suby1*d-a[i].y1);
else flip+=(subx1*d-a[i].x1)*(suby1*d-a[i].y1);
if(subx1%2==suby2%2)flip-=(subx1*d-a[i].x1)*(a[i].y2-suby2*d+1);
else flip+=(subx1*d-a[i].x1)*(a[i].y2-suby2*d+1);
if(subx2%2==suby1%2)flip-=(a[i].x2-subx2*d+1)*(suby1*d-a[i].y1);
else flip+=(a[i].x2-subx2*d+1)*(suby1*d-a[i].y1);
if(subx2%2==suby2%2)flip-=(a[i].x2-subx2*d+1)*(a[i].y2-suby2*d+1);
else flip+=(a[i].x2-subx2*d+1)*(a[i].y2-suby2*d+1);
int difx=subx2-subx1-1;
int dify=suby2-suby1-1;
if(difx%2==0 && dify%2==0)continue;
if(dify&1){
if(suby1%2==subx1%2)flip+=d*(subx1*d-a[i].x1);
else flip-=d*(subx1*d-a[i].x1);
if(suby1%2==subx2%2)flip+=d*(a[i].x2-subx2*d+1);
else flip-=d*(a[i].x2-subx2*d+1);
}
if(difx&1){
if(subx1%2==suby1%2)flip+=d*(suby1*d-a[i].y1);
else flip-=d*(suby1*d-a[i].y1);
if(subx1%2==suby2%2)flip+=d*(a[i].y2-suby2*d+1);
else flip-=d*(a[i].y2-suby2*d+1);
}
if(subx1%2==suby1%2)flip-=d*d;
else flip+=d*d;
}
}
ans=min({ans, flip, n*n-flip});
}
cout << ans << '\n';
}
