#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
#define MAXN 1000005
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;
#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {
while(L < R) cerr << *L << " \n"[next(L) == R], ++ L;
}
void kout() {cerr << endl;}
template<class T1, class ... T2> void kout(T1 a, T2 ... e) {
cerr << a << " ", kout(e...);
}
#else
#define print(...) 0
#define vprint(...) 0
#endif
struct sb2 {
int n, k;
struct pt {
int u, l, d, r;
};
vector<pt> a;
void init_(int _n, int _k) {
n = _n, k = _k;
a.assign(k + 1, {0, 0, 0, 0});
}
int solve() {
int ans[2];
ans[0] = ans[1] = 0;
rep(i, 1, k) {
int x, y;
x = a[i].u, y = a[i].l;
if((x & 1) == (y & 1)) ans[0] ++;
else ans[1] ++;
}
int cnt1 = ceil(n, 2) * ceil(n, 2) + (n / 2) * (n / 2);
int aa = cnt1 - ans[0] + ans[1];
int bb = n * n - cnt1 - ans[1] + ans[0];
return min(aa, bb);
}
} ;
struct sb1 {
int n, k;
struct pt {
int u, l, d, r;
};
vector<pt> a;
void init_(int _n, int _k) {
n = _n, k = _k;
a.assign(k + 1, {0, 0, 0, 0});
}
int solve() {
int ans = INF;
rep(i, 1, n - 1) {
if(n % i) continue;
int cnt = 0;
rep(j, 1, n / i) rep(m, 1, n / i) {
cnt += i * i * bool((j & 1) == (m & 1));
}
ans = min(ans, n * n - cnt);
}
return ans;
}
} ;
struct sb3 {
int n, k;
struct pt {
int u, l, d, r;
};
vector<pt> a;
void init_(int _n, int _k) {
n = _n, k = _k;
a.assign(k + 1, {0, 0, 0, 0});
}
int get(int x) {
return ceil(x, 2) * ceil(x, 2) + (x / 2) * (x / 2);
}
int cal(int x) {
assert(n % x == 0);
int ans[2]; ans[0] = 0, ans[1] = 0;
rep(i, 1, k) {
int u = a[i].u, l = a[i].l;
int uu = ceil(u, x) & 1, ll = ceil(l, x) & 1;
ans[(uu == ll)] ++;
}
int cc = get(n / x);
int cnt1 = x * x * cc + ans[0] - ans[1];
int cnt2 = ((n / x) * (n / x) - cc) * x * x + ans[1] - ans[0];
print(x, cnt1, cnt2, ans[0], ans[1]);
return min(cnt1, cnt2);
}
int solve() {
int kk = sqrt(n) + 1, ans = INF;
rep(i, 1, kk) {
if(n % i) continue;
if(i != n) ans = min(ans, cal(i));
if(n / i != n)ans = min(ans, cal(n / i));
}
return ans;
}
} ;
struct sb4 {
int n, k;
struct pt {
int u, l, d, r;
};
vector<pt> a;
void init_(int _n, int _k) {
n = _n, k = _k;
a.assign(k + 1, {0, 0, 0, 0});
}
int get(int x) {
return ceil(x, 2) * ceil(x, 2) + (x / 2) * (x / 2);
}
int pre(int x, int y, int v) {
int ans = 0, xx = ceil(x, v) - 1, yy = ceil(y, v) - 1;
if(x == 0 || y == 0) return 0;
ans += ceil(xx, 2) * ceil(yy, 2) * v * v + (xx / 2) * (yy / 2) * v * v;
// down
if(xx & 1) ans += (yy / 2) * (x - xx * v) * v;
else ans += ceil(yy , 2) * (x - xx * v) * v;
// right
if(yy & 1) ans += (xx / 2) * (y - yy * v) * v;
else ans += ceil(xx, 2) * (y - yy * v) * v;
// r0d
if((xx & 1) == (yy & 1)) ans += (x - xx * v) * (y - yy * v);
return ans;
}
int val(int u, int d, int l, int r, int v) {
int ans = pre(d, r, v) - pre(d, l - 1, v)
- pre(u - 1, r, v) + pre(u - 1, l - 1, v);
// print(u, d, l, r, v, ans);
return ans;
}
int cal(int x) {
assert(n % x == 0);
int ans[2]; ans[0] = 0, ans[1] = 0;
rep(i, 1, k) {
int u = a[i].u, l = a[i].l, d = a[i].d, r = a[i].r;
int area = (d - u + 1) * (r - l + 1);
ans[1] += val(u, d, l, r, x);
ans[0] += area - val(u, d, l, r, x);
}
int cc = get(n / x);
int cnt1 = x * x * cc + ans[0] - ans[1];
int cnt2 = ((n / x) * (n / x) - cc) * x * x + ans[1] - ans[0];
return min(cnt1, cnt2);
}
int solve() {
int kk = sqrt(n) + 1, ans = INF;
rep(i, 1, kk) {
if(n % i) continue;
if(i != n) ans = min(ans, cal(i));
if(n / i != n)ans = min(ans, cal(n / i));
}
return ans;
}
} ac;
int cal1(int u, int d, int l, int r, int v) {
int ans = 0;
rep(i, u, d) rep(j, l, r) {
ans += bool((ceil(i, v) & 1) == (ceil(j, v) & 1));
}
return ans;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, k; cin >> n >> k;
ac.init_(n, k);
rep(i, 1, k) {
cin >> ac.a[i].u >> ac.a[i].l;
cin >> ac.a[i].d >> ac.a[i].r;
}
cout << ac.solve() << "\n";
return 0;
}
