#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif
#define int long long
int f(int d, int s) {
int c = s / (2 * d);
int ret = c * d;
s %= 2 * d;
int mn = min(d, s);
ret += mn;
return ret;
}
int get(int d, int l, int r) {
return f(d, r + 1) - f(d, l);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> x1(k), y1(k), x2(k), y2(k);
for (int i = 0; i < k; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
x1[i]--; y1[i]--; x2[i]--; y2[i]--;
}
vector<int> v = {1};
for (int x = 2; x * x <= n; x++) {
if (n % x == 0) {
v.push_back(x);
if (x * x != n) {
v.push_back(n / x);
}
}
}
int ans = n * n;
for (int d : v) {
int c = (n * n / d / d + 1) / 2 * d * d;
for (int i = 0; i < k; i++) {
int w0 = get(d, y1[i], y2[i]);
int w1 = y2[i] - y1[i] + 1 - w0;
int l = x1[i], r = x2[i];
int h1 = get(d, l, r);
int h2 = r - l + 1 - h1;
c += h1 * (w1 - w0);
c += h2 * (w0 - w1);
}
ans = min(ans, c);
}
for (int d : v) {
int c = (n * n / d / d) / 2 * d * d;
for (int i = 0; i < k; i++) {
int w1 = get(d, y1[i], y2[i]);
int w0 = y2[i] - y1[i] + 1 - w1;
int l = x1[i], r = x2[i];
int h1 = get(d, l, r);
int h2 = r - l + 1 - h1;
c += h1 * (w1 - w0);
c += h2 * (w0 - w1);
}
ans = min(ans, c);
}
cout << ans << '\n';
return 0;
}
