#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
#define int long long
vector <vector <int>> rect;
int n, m;
int res = 1e18;
int f(int x, int y, int k) {
int cnt = 0;
int _x = (x / k) * k, _y = (y / k) * k;
if ((_x / k + _y / k) & 1) {
cnt += ((_x / k) * (_y / k)) / 2 * (k * k);
cnt += ((_y / k) + 1) / 2 * (x - _x) * k;
cnt += ((_x / k) + 1) / 2 * (y - _y) * k;
}
else {
cnt += ((_x / k) * (_y / k) + 1) / 2 * (k * k);
cnt += ((_y / k)) / 2 * (x - _x) * k;
cnt += ((_x / k)) / 2 * (y - _y) * k;
cnt += (x - _x) * (y - _y);
}
return cnt;
}
void solve(int k) {
int ans = (n * n - f(n, n, k));
for (auto x : rect) {
int x1 = x[0], y1 = x[1], x2 = x[2], y2 = x[3];
int w = f(x2, y2, k) + f(x1 - 1, y1 - 1, k) - f(x2, y1 - 1, k) - f(x1 - 1, y2, k);
ans += w;
ans -= (x2 - x1 + 1) * (y2 - y1 + 1) - w;
}
res = min({res, ans, n * n - ans});
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#ifdef JASPER
freopen("in1", "r", stdin);
#endif
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
rect.push_back({x1, y1, x2, y2});
}
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
solve(i);
if (i != n / i && i > 1)
solve(n / i);
}
}
cout << res << "\n";
}
