#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int N = 1e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
pair <int, int> a[N], b[N];
int par[2 * N];
int lim[2 * N];
int n,k;
int getc(int i, int j, int l, int val) {
return ((par[i] ^ par[j]) & 1) ^ val;
}
int getv(int i, int j, int l, int val) {
return (getc(i, j, l, val) > 0) ? -1 : 1;
}
long long calc(int x, int y, int u, int v, int l, int val) {
if (x > u || y > v)
return 0;
long long res = 0;
int dx = (u - x + 1);
int dy = (v - y + 1);
int base = getv(x, y, l, val);
if (dx > dy)
swap(dx, dy);
if (dx < l) {
if (dy < l)
res = (long long) dx * dy;
else {
if (par[dy] & 1)
res = (long long) dx * l;
}
} else {
if (par[dx] & par[dy] & 1)
res = (long long) l * l;
}
if (base < 0)
res = -res;
return res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef ONLINE_JUDGE
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
#endif
cin >> n >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i].fi >> a[i].se >> b[i].fi >> b[i].se;
a[i].fi--; a[i].se--;
b[i].fi--; b[i].se--;
}
long long ans = ooo;
for (int l = 1; l < n; l++) if (n % l == 0)
for (int val = 0; val < 2; val++) {
int d = (n / l);
long long res = ((1LL * d * d + val) >> 1) * l * l;
for (int i = 0; i < 2 * n; i++) {
par[i] = (i / l);
lim[i] = par[i] * l;
}
for (int id = 1; id <= k; id++) {
int x = a[id].fi;
int y = a[id].se;
int u = b[id].fi;
int v = b[id].se;
int i = lim[x + l - 1];
int j = lim[y + l - 1];
int s = lim[u + 1] - 1;
int t = lim[v + 1] - 1;
vector <pair <int, int>> r, c;
if (par[x] == par[u])
r.push_back(mp(x, u));
else {
r.push_back(mp(x, i - 1));
if (i <= s)
r.push_back(mp(i, s));
r.push_back(mp(s + 1, u));
}
if (par[y] == par[v])
c.push_back(mp(y, v));
else {
c.push_back(mp(y, j - 1));
if (j <= t)
c.push_back(mp(j, t));
c.push_back(mp(t + 1, v));
}
for (pair <int, int> a : r)
for (pair <int, int> b : c)
res += calc(a.fi, b.fi, a.se, b.se, l, val);
}
// cerr << "split: " << l << " " << val << " " << res << "\n";
mini(ans, res);
}
cout << ans;
return 0;
}
