#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second
const ll INF = 1e12;
using namespace std;
struct data
{
ll x, y1, y2; bool t;
inline bool operator<(const data& r) const
{
return make_pair(make_pair(x, y1), make_pair(y2, t)) < make_pair(make_pair(r.x, r.y1), make_pair(r.y2, r.t));
}
};
int N, K;
ll S, p1, p2, ans = INF;
vector<data> A;
inline void a1(ll Y1, ll Y2, ll v)
{
ll R = Y2 / (2 * S), L = Y1 / (2 * S), a = 0;
if (L == R) {a += max(0LL, min(Y2 + 1, 2 * L * S + S) - Y1); }
else
{
a += (R - L - 1) * S;
a += max(0LL, 2 * L * S + S - Y1);
a += min(Y2 + 1, 2 * R * S + S) - 2 * R * S;
}
p1 += a * v;
}
inline void a2(ll Y1, ll Y2, ll v)
{
ll R = Y2 / (2 * S), L = Y1 / (2 * S), a = 0;
if (L == R) {a += max(0LL, Y2 + 1 - max(Y1, 2 * L * S + S)); }
else
{
a += (R - L - 1) * S;
a += 2 * (L + 1) * S - max(Y1, 2 * L * S + S);
a += max(0LL, Y2 + 1 - 2 * R * S - S);
}
p2 += a * v;
}
void solve()
{
p1 = 0; p2 = 0;
ll s1 = 0, s2 = 0, t1 = 0, t2 = 0; int j = 0;
for (int i = 0; i < N; i++)
{
for (; j < A.size() && A[j].x <= i; j++)
{
if (A[j].t)
{
a1(A[j].y1, A[j].y2, -1);
a2(A[j].y1, A[j].y2, -1);
}
else
{
a1(A[j].y1, A[j].y2, 1);
a2(A[j].y1, A[j].y2, 1);
}
}
t1 += p1; t2 += p2;
if ((i + 1) % S == 0)
{
ll c = (N / S + 1) / 2, f = (N / S) / 2; c *= S * S; f *= S * S;
if (i / S % 2 == 0)
{
s1 += (c - t1) + t2;
s2 += t1 + (f - t2);
}
else
{
s2 += (c - t1) + t2;
s1 += t1 + (f - t2);
}
t1 = 0; t2 = 0;
}
}
ans = min(ans, min(s1, s2));
}
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K;
for (int i = 0; i < K; i++)
{
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
data a; a.x = x1 - 1; a.y1 = y1 - 1; a.y2 = y2 - 1; a.t = 0;
data b; b.x = x2; b.y1 = y1 - 1; b.y2 = y2 - 1; b.t = 1;
A.push_back(a); A.push_back(b);
}
sort(A.begin(), A.end());
for (int i = 1; i * i <= N; i++)
{
if (N % i == 0)
{
S = i; solve();
if (i * i < N && i > 1) {S = N / i; solve();}
}
}
cout << ans << "\n";
return 0;
}
