#include "bits/stdc++.h"
using namespace std;
#define int long long
#pragma GCC optimize ("O3")
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'
/*
implement and debug smart
DONT GET STUCK ON ONE APPROACH
write smth on paper
edge cases (n=1?)
rewrite the problem
simplify
transform the problem into other problem
*/
void solve(){
int n,k;
cin >> n >> k;
vector<array<int,4>> v;
int ans = n * n;
for(int i=1;i<=k;i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
a--;
b--;
c--;
d--;
v.pb({a,b,c,d});
}
auto f = [](array<int,4> a,array<int,4> b)->array<int,4>{
int xl,xr,yl,yr;
xl=max(a[0],b[0]);
xr=min(a[2],b[2]);
yl=max(a[1],b[1]);
yr=min(a[3],b[3]);
if(xl<=xr && yl<=yr) return {xl,yl,xr,yr};
else return {-1,-1,-1,-1};
};
for(int i=1;i<n;i++){
if(n%i) continue;
// 1 siyah
// 0 beyaz
int cur = 0;
map<array<int,2>,vector<array<int,4>>> mp;
int kac_siyah = (n / i) * ( (n / i) / 2);
if((n/i)&1) kac_siyah += (n / i) / 2;
for(auto x : v){
int aa = x[0]-(x[0]%i);
int bb = x[1]-(x[1]%i);
for(int a=aa;a<=n;a+=i){
for(int b=bb;b<=n;b+=i){
if(f(x,{a,b,a+i-1,b+i-1})[0]!=-1)
mp[{a,b}].pb(f(x,{a,b,a+i-1,b+i-1}));
else break;
}
}
}
for(auto x:mp){
int col = (x.first[0] / i + x.first[1] / i) & 1;
int hm = 0;
for(auto y:x.second) hm+=(y[2]-y[0]+1)*(y[3]-y[1]+1);
if(col) cur+=i*i-hm;
else cur+=hm;
if(col) kac_siyah--;
}
//cout << i << ": " << kac_siyah << endl;
cur += kac_siyah * i * i;
ans=min(ans,cur);
cur=0;
kac_siyah = (n / i) * ( (n/i) / 2);
if((n/i)&1) kac_siyah += (n / i + 1) / 2;
for(auto x:mp){
int col = (x.first[0] / i + x.first[1] / i) & 1;
col^=1;
int hm = 0;
for(auto y:x.second) hm+=(y[2]-y[0]+1)*(y[3]-y[1]+1);
if(col) cur+=i*i-hm;
else cur+=hm;
if(col) kac_siyah--;
}
cur += kac_siyah * i * i;
//cout << i << ": " << kac_siyah << endl;
ans=min(ans,cur);
}
cout << ans << endl;
}
int32_t main(){
cin.tie(0);
ios::sync_with_stdio(0);
int t=1;//cin >> t;
while(t--) solve();
}
