#include <iostream>
#include <cstdio>
using namespace std;
#define m_p make_pair
const int N = 100005;
struct ban
{
int x, y;
ban(){}
ban(int x, int y)
{
this->x = x;
this->y = y;
}
};
int n;
int m;
pair<ban, ban> a[N];
bool vv;
bool sevv(int x, int y, int t)
{
x = x / t;
y = y / t;
if ((x + y) % 2 == 0)
{
if (vv)
return true;
else
return false;
}
else
{
if (vv)
return false;
else
return true;
}
}
long long sev(const pair<ban, ban>& a, int t)
{
int x1 = a.first.x;
int y1 = a.first.y;
int x2 = a.second.x;
int y2 = a.second.y;
if (x1 == x2 && y1 == y2)
return sevv(x1, y1, t);
int xm1 = (x1 / t + 1) * t;
if (x1 % t == 0)
xm1 = x1;
int xm2 = (x2 / t) * t - 1;
if (x2 % t == t - 1)
xm2 = x2;
int ym1 = (y1 / t + 1) * t;
if (y1 % t == 0)
ym1 = y1;
int ym2 = (y2 / t) * t - 1;
if (y2 % t == t - 1)
ym2 = y2;
long long ans = 0;
long long xx = 0;
if (xm1 - xm2 == t + 1)
{
if (sevv(x1, y1, t))
xx = (x2 - x1 + 1);
goto kovx;
}
// x1; xm1 - 1
if (sevv(x1, y1, t))
xx += (xm1 - x1);
// xm1; xm2
if (sevv(xm1, y1, t))
xx += ((((xm2 - xm1 + 1) / t) / 2) * t);
else
xx += ((((xm2 - xm1 + 1) / t) - (((xm2 - xm1 + 1) / t) / 2)) * t);
// xm2 + 1; x2
if (sevv(xm2 + 1, y1, t))
xx += (x2 - xm2);
kovx:
if (ym1 - ym2 == t + 1)
{
ans += (xx * (y2 - y1 + 1));
goto kovy;
}
// y1; ym1 - 1
if (sevv(x1, y1, t))
ans += ((ym1 - y1) * xx);
// ym1; ym2
ans += ((((ym2 - ym1 + 1) / t) / 2) * xx * t);
ans += ((((ym2 - ym1 + 1) / t) - (((ym2 - ym1 + 1) / t) / 2)) * ((x2 - x1 + 1) - xx) * t);
// ym2 + 1; y2
if (sevv(x1, y1, t) == sevv(x1, y2, t))
ans += ((y2 - ym2) * xx);
else
ans += ((y2 - ym2) * ((x2 - x1 + 1) - xx));
kovy:
return ans;
}
long long spi(const pair<ban, ban>& a, int t)
{
int x1 = a.first.x;
int y1 = a.first.y;
int x2 = a.second.x;
int y2 = a.second.y;
return 1LL * (x2 - x1 + 1) * (y2 - y1 + 1) - sev(a, t);
}
long long ans;
void stg(int t)
{
vv = true;
long long yans = 0;
long long g = 0;
for (int i = 0; i < m; ++i)
{
yans += (spi(a[i], t));
g += (sev(a[i], t));
}
yans += (sev(m_p(ban(0, 0), ban(n - 1, n - 1)), t) - g);
ans = min(ans, yans);
vv = false;
yans = 0;
g = 0;
for (int i = 0; i < m; ++i)
{
yans += (spi(a[i], t));
g += (sev(a[i], t));
}
yans += (sev(m_p(ban(0, 0), ban(n - 1, n - 1)), t) - g);
ans = min(ans, yans);
}
int main()
{
//freopen("input2.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d%d", &a[i].first.x, &a[i].first.y, &a[i].second.x, &a[i].second.y);
--a[i].first.x;
--a[i].first.y;
--a[i].second.x;
--a[i].second.y;
}
ans = 1LL * n * n;
for (int i = 1; i * i <= n; ++i)
{
if (n % i == 0)
{
if (i != n)
stg(i);
if (n / i != n)
stg(n / i);
}
}
cout << ans << endl;
return 0;
}
