// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using ll = long long;
const ll INFL = ll(1e18) + 10;
int main() {
cin.tie(0)->sync_with_stdio(0);
// ONLY SQRT(N) WIDTHS
int N, K; cin >> N >> K;
V<AR<int, 4>> A(K);
for(auto& x : A) cin >> x[0] >> x[1] >> x[2] >> x[3];
V<int> div;
for(int i = 1; i*i <= N; i++) {
if (N % i == 0) {
div.pb(i);
if (i*i != N) div.pb(N / i);
}
}
sort(begin(div), end(div)); div.pop_back();
ll ans = INFL;
for(auto& w : div) {
int n = N / w;
AR<ll, 2> res = {((n * 1LL * n) / 2) * w * 1LL * w, ((n * 1LL * n + 1) / 2) * w * 1LL * w};
// res[0] -> top-left is white, res[1] -> top-left is black
for(auto x : A) {
auto [r, c, R, C] = x; --r, --c, --R, --C;
// BLACK AND WHITE PER ROW (FOR FIRST ROW)
int BPR = 0, WPR = 0;
// CHECK (r, c) and (r, C)
int wr = r / w, wc = c / w, wC = C / w, wR = R / w;
int Crc = (wr + wc) % 2, CrC = (wr + wC) % 2;
if (wc == wC) (Crc == 0 ? WPR += C - c + 1 : BPR += C - c + 1);
else {
int LB = (wc + 1) * w - 1;
(Crc == 0 ? WPR += LB - c + 1 : BPR += LB - c + 1);
int RB = wC * w;
(CrC == 0 ? WPR += C - RB + 1 : BPR += C - RB + 1);
int LEN = (RB - 1) - (LB + 1) + 1;
assert(LEN % w == 0); int BLK = LEN / w;
if (Crc == 0) BPR += ((BLK + 1) / 2) * w, WPR += (BLK / 2) * w;
else WPR += ((BLK + 1) / 2) * w, BPR += (BLK / 2) * w;
}
// OBVERSED AND INVERSED ROWS
int OPR = 0, IPR = 0;
if (wr == wR) OPR += R - r + 1;
else {
int LB = (wr + 1) * w - 1;
OPR += LB - r + 1;
int LEN = R - (LB + 1) + 1;
int BLK = LEN / w; int LEFT = LEN % w;
IPR += ((BLK + 1) / 2) * w; OPR += (BLK / 2) * w;
if (BLK % 2) OPR += LEFT;
else IPR += LEFT;
}
ll BLACKS = BPR * 1LL * OPR + WPR * 1LL * IPR;
ll WHITES = WPR * 1LL * OPR + BPR * 1LL * IPR;
// cout << BLACKS << " - " << WHITES << nl;
res[0] += WHITES - BLACKS; res[1] += BLACKS - WHITES;
}
// cout << res[0] << " " << res[1] << nl;
ans = min(ans, min(res[0], res[1]));
}
cout << ans << nl;
return 0;
}
