#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
/*
ll pw(ll a, ll b) {
ll ans = 1; while (b) {
while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
ans = (ans * a) % MOD, --b;
} return ans;
}
*/
pair<ll, ll> operator+(pair<ll, ll> a, pair<ll, ll> b) {
return make_pair(a.first + b.first, a.second + b.second);
}
pair<ll, ll> operator-(pair<ll, ll> a, pair<ll, ll> b) {
return make_pair(a.first - b.first, a.second - b.second);
}
pair<ll, ll> get(ll x, ll k) {
ll kx = x / k;
if (kx % 2 == 0)
return make_pair((kx + 1) / 2 * k + x % k, (kx) / 2 * k);
else
return make_pair((kx + 1) / 2 * k, (kx) / 2 * k + x % k);
}
const ll MAXN = 120000;
int n, k;
vector<ll> dv;
pair<ll, ll> go[MAXN];
int main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i < n; ++i) {
if (n % i == 0)
dv.push_back(i);
}
for (int i = 0; i < k; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
--x1, --y1;
for (int it = 0; it < dv.size(); ++it) {
int j = dv[it];
pair<ll, ll> xx = get(x2, j) - get(x1, j);
pair<ll, ll> yy = get(y2, j) - get(y1, j);
go[it] = go[it] + make_pair(xx.first * yy.first + xx.second * yy.second, xx.second * yy.first + xx.first * yy.second);
}
}
ll ans = ll(n) * n;
for (int i = 0; i < dv.size(); ++i) {
ll sd = n / dv[i];
pair<ll, ll> nd = make_pair((sd * sd + 1) / 2 * dv[i] * dv[i], (sd * sd) / 2 * dv[i] * dv[i]);
ans = min(ans, nd.first - go[i].first + go[i].second);
ans = min(ans, nd.second - go[i].second + go[i].first);
}
cout << ans << "\n";
return 0;
}
