// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>
#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif
using namespace std ;
using ll = long long ;
#define int ll
bool isPrime(int x) {
if (x < 2) return 0 ;
for (int i = 2 ; i * i <= x ; i++) {
if (x % i == 0) {
return 0 ;
}
}
return 1 ;
}
struct Fenwick {
vector<ll> t ;
int n;
Fenwick(int len) {
n = len ;
t.assign(n + 1, 0) ;
}
void upd(int i, ll x) {
while (i <= n) {
t[i] += x;
i += (i & (-i)) ;
}
}
ll get(int i) {
ll sum = 0 ;
while (i) {
sum += t[i] ;
i -= (i & (-i)) ;
}
return sum ;
}
ll get(int l, int r) {
return get(r) - get(l - 1) ;
}
};
int32_t main() {
cin.tie(0)->sync_with_stdio(false) ;
ll n, k ; cin >> n >> k ;
struct rect {
int x1, y1, x2, y2;
void read() {
cin >> x1 >> y1 >> x2 >> y2 ;
x1-- , y1-- , x2-- , y2-- ;
}
};
vector<rect> a(k) ;
for (int i = 0 ; i < k ; i++) a[i].read() ;
vector<int> d;
for (int i = 1 ; i * i <= n ; i++) {
if (n % i) continue ;
d.push_back(i) ;
if (n / i != i) d.push_back(n / i) ;
}
auto calc = [&](ll del) -> ll{
vector<vector<ll>> cnt(del + 1, vector<ll>(2, 0)) ;
int block = n / del ;
vector<Fenwick> f(2, Fenwick(n + 2)) ;
for (int i = 0 ; i < k ; i++) {
int x1 = a[i].x1 , y1 = a[i].y1 , x2 = a[i].x2, y2 = a[i].y2 ;
ll leny = (y2 - y1 + 1) ;
ll lenx = (x2 - x1 + 1) ;
ll bL = y1 / block , bR = y2 / block ;
ll even = 0 , odd = 0 ;
if (bL == bR) {
if (bL & 1) {
odd += leny;
} else {
even += leny ;
}
} else {
ll ost = bR - bL - 1 ;
if (ost > 0) {
if ((bL + 1) & 1) {
even += (ost / 2) * block ;
odd += (ost + 1) / 2 * block ;
} else {
even += (ost + 1) / 2 * block ;
odd += (ost / 2) * block ;
}
}
ll L = y1, R = (bL + 1) * block - 1 ;
ll LN = (R - L + 1) ;
if (bL & 1) {
odd += LN ;
} else {
even += LN ;
}
L = bR * block , R = y2 ;
LN = (R - L + 1) ;
if (bL & 1) {
odd += LN ;
} else {
even += LN ;
}
}
dbg(even , odd) ;
f[0].upd(x1 + 1, even) ;
f[0].upd(x2 + 2, -even) ;
f[1].upd(x1 + 1, odd) ;
f[1].upd(x2 + 2, -odd) ;
}
for (int i = 1 ; i <= n ; i++) {
// dbg(f[0].get(i), f[1].get(i)) ;
cnt[(i - 1) / block][0] += f[0].get(i) ;
cnt[(i - 1) / block][1] += f[1].get(i) ;
}
// dbg(del, cnt) ;
ll ret = 0 , sum = 0 ;
for (int i = 0 ; i < del ; i++) {
// for (int j = 0 ; j < del ; j++) {
if (i % 2 == 0) {
ll c = ((del + 1) / 2) * (block * block) ;
ll cur = c - cnt[i][0] + cnt[i][1] ;
sum += cur ;
} else {
ll c = (del / 2) * (block * block) ;
ll cur = c - cnt[i][1] + cnt[i][0] ;
sum += cur ;
}
// }
}
ret = sum ;
sum = 0 ;
for (int i = 0 ; i < del ; i++) {
// for (int j = 0 ; j < del ; j++) {
if (i % 2 != 0) {
ll c = ((del + 1) / 2) * (block * block) ;
ll cur = c - cnt[i][0] + cnt[i][1] ;
sum += cur ;
} else {
ll c = (del / 2) * (block * block) ;
ll cur = c - cnt[i][1] + cnt[i][0] ;
sum += cur ;
}
// }
}
ret = min(ret, sum) ;
return ret ;
};
ll ret = LLONG_MAX ;
for (int i : d) {
if (i > 1) {
ret = min(ret, calc(i)) ;
}
}
cout << ret ;
return 0 ;
}
// 希望白银
