#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <cstring>
#include <array>
#include <bitset>
#include <cassert>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
array < int, 4 > l[maxn];
ll n, k;
inline ll dodaj(ll val, int br, bool p){
if((br&1 && p) || (!(br&1) && !p)){
return val;
}
return 0;
}
bool stima(int br, bool p){
return (br&1 && p) || (!(br&1) && !p);
}
ll probaj(ll val, bool p){
ll br=0;
ll x1, y1, x2, y2;
ll pocx, pocy, krajx, krajy;
ll cor1, cor2, cor3, cor4;
for(int i=0; i<k; i++){
x1=l[i][0];
y1=l[i][1];
x2=l[i][2];
y2=l[i][3];
pocx=x1/val;
pocy=y1/val;
krajx=x2/val;
krajy=y2/val;
if(pocx==krajx && pocy==krajy){
// cout << "izi!" << endl;
br+=dodaj((x2-x1+1)*(y2-y1+1), pocx+pocy, p);
}
else if(pocx==krajx){
// cout << "tu sam!" << endl;
cor1=x1;
cor2=y1;
cor3=min(x2, (pocx+1)*val-1);
cor4=min(y2, (pocy+1)*val-1);
// cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' ' << cor4 << endl;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
cor1=max(x1, krajx*val);//
cor2=max(y1, krajy*val);//fixaj svugdje! bilo je poc
cor3=x2;
cor4=y2;
// cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' ' << cor4 << endl;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+krajy, p); //fixaj i ovo
pocy++;
krajy--;
if(pocy>krajy){
continue;
}
cor1=x1;
cor2=pocy*val;
cor3=x2;
cor4=(pocy+1)*val-1;
// cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' ' << cor4 << endl;
// cout << pocy << ' ' << krajy << endl;
if(stima(pocx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+2)/2);
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+1)/2);
}
}
else if(pocy==krajy){
// cout << "ovdje!" << endl;
cor1=x1;
cor2=y1;
cor3=min(x2, (pocx+1)*val-1);
cor4=min(y2, (pocy+1)*val-1);
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
cor1=max(x1, krajx*val);
cor2=max(y1, krajy*val);
cor3=x2;
cor4=y2;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+krajy, p);
pocx++;
krajx--;
if(pocx>krajx){
continue;
}
cor1=pocx*val;
cor2=y1;
cor3=(pocx+1)*val-1;
cor4=y2;
if(stima(pocx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+2)/2);
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+1)/2);
}
}
else{
// cout << "kunito!" << endl;
cor1=x1;
cor2=y1;
cor3=min(x2, (pocx+1)*val-1);
cor4=min(y2, (pocy+1)*val-1);
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
cor1=max(x1, krajx*val);
cor2=max(y1, krajy*val);
cor3=x2;
cor4=y2;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+krajy, p);
cor1=x1;
cor2=max(y1, krajy*val);
cor3=min(x2, (pocx+1)*val-1);
cor4=y2;
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+krajy, p);
cor1=max(x1, krajx*val);
cor2=y1;
cor3=x2;
cor4=min(y2, (pocy+1)*val-1);
br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+pocy, p);
// cout << br << endl;
pocx++;
krajx--;
if(krajx>=pocx){
cor1=pocx*val;
cor2=y1;
cor3=(pocx+1)*val-1;
cor4=(pocy+1)*val-1;
// cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' '<< cor4 << endl;
// cout << pocx << ' ' << pocy << endl;
if(stima(pocx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+2)/2);
}
else{
// cout << "uso" << endl;
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+1)/2);
// cout << br << endl;
}
cor2=krajy*val;
cor4=y2;
if(stima(pocx+krajy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+2)/2);
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+1)/2);
}
}
pocx--;
krajx++;
pocy++;
krajy--;
if(krajy>=pocy){
cor1=x1;
cor2=pocy*val;
cor3=(pocx+1)*val-1;
cor4=(pocy+1)*val-1;
if(stima(pocx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+2)/2);
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+1)/2);
}
cor1=krajx*val;
cor3=x2;
if(stima(krajx+pocy, p)){
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+2)/2);
}
else{
br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+1)/2);
}
}
pocy--;
krajy++;
// cout << br << endl;
if(((pocx+pocy)&1 && p) || (!((pocx+pocy)&1) && !p)){
br+=((krajx-pocx-1)*(krajy-pocy-1)+1)/2*val*val;
}
else{
br+=(krajx-pocx-1)*(krajy-pocy-1)/2*val*val;
}
}
}
// cout << br << endl;
return br;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
ll uk=0;
int a, b, c, d;
// cout << "proso" << endl;
for(int i=0; i<k; i++){
// cout << "uso" << endl;
cin >> a >> b >> c >> d;
a--;
b--;
c--;
d--;
uk+=(ll)(c-a+1)*(d-b+1);
l[i]={a, b, c, d};
}
ll sol=1e18;
ll br1, br2;
ll crno, bijelo;
for(ll i=1; i*i<=n; i++){
// cout << "na " << i << endl;
if(n%i==0){
br1=probaj(i, 0);
br2=probaj(i, 1);
crno=((n/i)*(n/i)+1)/2*i*i;
bijelo=(n/i)*(n/i)/2*i*i;
// cout << "boje " << bijelo << ' ' << crno << endl;
// cout << "brojevi " << br1 << ' ' << br2 << endl;
sol=min(sol, crno-br1+uk-br1);
swap(crno, bijelo);
sol=min(sol, crno-br2+uk-br2);
if(i!=1 && i*i!=n){
br1=probaj(n/i, 0);
br2=probaj(n/i, 1);
crno=(i*i+1)/2*(n/i)*(n/i);
bijelo=i*i/2*(n/i)*(n/i);
sol=min(sol, crno-br1+uk-br1);
swap(crno, bijelo);
sol=min(sol, crno-br2+uk-br2);
}
}
}
cout << sol << '\n';
return 0;
}
