#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 ret = (s / (2 * d)) * d;
s %= 2 * d;
int mn = min(d, s);
return ret + mn;
}
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]--;
}
int ans = n * n;
for (int d = 1; d < n; d++) {
if (n % d != 0) {
continue;
}
int c1 = (n * n / d / d + 1) / 2 * d * d;
int c2 = (n * n / d / d) / 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;
c1 += h1 * (w1 - w0);
c1 += h2 * (w0 - w1);
c2 += h1 * (w0 - w1);
c2 += h2 * (w1 - w0);
}
ans = min(ans, c1);
ans = min(ans, c2);
}
cout << ans << '\n';
return 0;
}
