// -- //
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define pll pair<ll, ll>
#define ppll pair<pll, pll>
#define x first
#define y second
using namespace std;
typedef long long rll;
typedef int ll;
const ll N = 1e5+228;
ppll a[N];
vector<pll> add[N], del[N];
ll n, k;
rll res;
inline void ch(ll m, ll bln) __attribute__((always_inline));
inline void ch(ll m, ll bln){
rll bob=0, bow=0;
rll no[2]={0};
for(ll i = 1;i<=n;i++){
for(auto &j : add[i]){
ll s = j.x, e = j.y;
--s, e--;
ll bs = s/m, be = e/m;
rll bse = ((rll)bs+1)*m-1;
if(bs==be) no[bs&1] += e-s+1;
else if(bs+1==be){
no[bs&1] += bse-s+1;
no[be&1] += e-bse;
}else{
no[bs&1] += bse-s+1;
no[be&1] += e-bse;
bs++, be--;
ll kb = (be-bs+1)/2;
no[bs&1] += ((rll)(be-bs+1-kb))*m;
no[be&1] += ((rll)kb)*m;
}
}
if(((i-1)/m)&1){
bow+=no[0], bob+=no[1];
}else{
bob+=no[0], bow+=no[1];
}
for(auto &j : del[i]){
ll s = j.x, e = j.y;
--s, e--;
ll bs = s/m, be = e/m;
rll bse = ((rll)bs+1)*m-1;
if(bs==be) no[bs&1] -= e-s+1;
else if(bs+1==be){
no[bs&1] -= bse-s+1;
no[be&1] -= e-bse;
}else{
no[bs&1] -= bse-s+1;
no[be&1] -= e-bse;
bs++, be--;
ll kb = (be-bs+1)/2;
no[bs&1] -= ((rll)(be-bs+1-kb))*m;
no[be&1] -= ((rll)kb)*m;
}
}
}
rll mbb = 1LL*((rll)(bln>>1))*((rll)m)*((rll)n)+1LL*((rll)((bln&1) ? (bln+1)>>1 : 0))*((rll)m)*((rll)m);
rll v1 = (mbb-bob)+bow;
rll v2 = bob+(((rll)n*n)-mbb-bow);
if(v1<res) res=v1;
if(v2<res) res=v2;
}
signed main(){
cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
cin >> n >> k;
for(ll i =0 ;i<k;i++){
cin >> a[i].x.x >> a[i].x.y >> a[i].y.x >> a[i].y.y;
add[a[i].x.y].push_back({a[i].x.x, a[i].y.x});
del[a[i].y.y].push_back({a[i].x.x, a[i].y.x});
}
res=(rll)n*n;
for(ll i = 1;i*i<=n;i++){
ll k = n/i;
if(n-k*i) continue;
ch(i, k);
if(i>1) ch(k, i);
}
cout<<res;
}
