#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
#define int long long
using namespace std;
const ll maxn=1e6+5, inf=1e18;
struct Rect{
int x1, y1, x2, y2;
};
int n, k;
ll ans;
Rect a[maxn];
int CC(int i, int j, int c00){
return (int)((i + j) % 2 == 1) ^ c00;
}
ll calc(int sz, int x1, int x2, int y1, int y2, int c00){
if(x1 > x2 || y1 > y2) return 0;
int li = x1 / sz, ri = x2 / sz;
int lj = y1 / sz, rj = y2 / sz;
int col = CC(li, lj, c00);
ll cur = 0;
if(li == ri){
if(lj == rj){
if(!col) cur += 1LL * (x2 - x1 + 1) * (y2 - y1 + 1);
else cur -= 1LL * (x2 - x1 + 1) * (y2 - y1 + 1);
}else{
ll yleft = (lj + 1) * sz - 1;
if(col){
cur -= (x2 - x1 + 1) * (yleft - y1 + 1);
}else{
cur += (x2 - x1 + 1) * (yleft - y1 + 1);
}
if((rj - lj + 1) % 2 != 0){
if(col) cur += 1LL * (x2 - x1 + 1) * sz;
else cur -= 1LL * (x2 - x1 + 1) * sz;
}
ll yright = rj * sz;
if(CC(ri, rj, c00)){
cur -= (x2 - x1 + 1) * (y2 - yright + 1);
}else{
cur += (x2 - x1 + 1) * (y2 - yright + 1);
}
}
return cur;
}
if(lj == rj){
ll xtop = (li + 1) * sz - 1;
if(col){
cur -= (xtop - x1 + 1) * (y2 - y1 + 1);
}else{
cur += (xtop - x1 + 1) * (y2 - y1 + 1);
}
if((ri - li + 1) % 2 != 0){
if(col) cur += 1LL * (y2 - y1 + 1) * sz;
else cur -= 1LL * (y2 - y1 + 1) * sz;
}
ll xbottom = ri * sz;
if(CC(ri, rj, c00)){
cur -= (x2 - xbottom + 1) * (y2 - y1 + 1);
}else{
cur += (x2 - xbottom + 1) * (y2 - y1 + 1);
}
return cur;
}
if(x1 % sz != 0 || (x2 + 1) % sz != 0){
int x1top = (li+1) * sz - 1;
int x1bottom = ri * sz;
return calc(sz, x1, x1top, y1, y2, c00) + calc(sz, x1top+1, x1bottom-1, y1, y2, c00) + calc(sz, x1bottom, x2, y1, y2, c00);
}
if(y1 % sz != 0 || (y2 + 1) % sz != 0){
int yleft = (lj + 1) * sz - 1;
int yright = rj * sz;
return calc(sz, x1, x2, y1, yleft, c00) + calc(sz, x1, x2, yleft+1, yright-1, c00) + calc(sz, x1, x2, yright, y2, c00);
}
if((ri - li + 1) % 2 != 0 && (rj - lj + 1) % 2 != 0){
if(col) cur -= 1LL * sz * sz;
else cur += 1LL * sz * sz;
}
return cur;
}
void solve(int sz, int c00){
ll cur = 0;
f1(i,k){
int x1 = a[i].x1, x2 = a[i].x2, y1 = a[i].y1, y2 = a[i].y2;
cur += calc(sz, x1, x2, y1, y2, c00);
}
ll v = 1LL * (n / sz) * (n / sz);
cur += (v / 2) * sz * sz;
if(v % 2 == 1 && c00) cur += sz * sz;
// cout << sz << ' ' << cur << endl;
ans = min(ans, cur);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if(fopen(__file_name ".inp", "r")){
freopen(__file_name ".inp", "r", stdin);
freopen(__file_name ".out", "w", stdout);
}
// code here
cin >> n >> k;
f1(i,k){
cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
a[i].x1--; a[i].y1--; a[i].x2--; a[i].y2--;
}
ans = inf;
for(int i = 1; i * i <= n; i++){
if(n % i == 0){
solve(i, 0);
solve(i, 1);
if(i * i != n && i != 1){
solve(n / i, 0);
solve(n / i, 1);
}
}
}
cout << ans;
return 0;
}
