#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;
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;
// y1; ym1 - 1
// x1; xm1 - 1
long long xx = 0;
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);
if (xm1 - xm2 == t + 1)
{
xx = 0;
if (sevv(x1, y1, t))
xx = (x2 - x1 + 1);
}
ans += ((ym1 - y1) * xx);
// ym1; ym2
// x1; xm1 - 1
xx = 0;
if (sevv(x1, ym1, t))
xx += (xm1 - x1);
// xm1; xm2
if (!sevv(xm1, ym1, 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, ym1, t))
xx += (x2 - xm2);
if (xm1 - xm2 == t + 1)
{
xx = 0;
if (sevv(x1, ym1, t))
xx = (x2 - x1 + 1);
}
ans += ((((ym2 - ym1 + 1) / t) / 2) * ((x2 - x1 + 1) - xx) * t);
ans += ((((ym2 - ym1 + 1) / t) - (((ym2 - ym1 + 1) / t) / 2)) * xx * t);
// ym2 + 1; y2
// x1; xm1 - 1
xx = 0;
if (sevv(x1, ym2 + 1, t))
xx += (xm1 - x1);
// xm1; xm2
if (!sevv(xm1, ym2 + 1, 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, ym2 + 1, t))
xx += (x2 - xm2);
if (xm1 - xm2 == t + 1)
{
xx = 0;
if (sevv(x1, ym2 + 1, t))
xx = (x2 - x1 + 1);
}
ans += ((y2 - ym2) * xx);
if (ym1 - ym2 == t + 1)
{
ans = 0;
xx = 0;
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);
if (xm1 - xm2 == t + 1)
{
xx = 0;
if (sevv(x1, y1, t))
xx = (x2 - x1 + 1);
}
ans += (xx * (y2 - y1 + 1));
}
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)
{
long long spii = spi(a[i], t);
yans += (spii);
g += (1LL * (a[i].second.x - a[i].first.x + 1) * (a[i].second.y - a[i].first.y + 1) - spii);
}
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)
{
long long spii = spi(a[i], t);
yans += (spii);
g += (1LL * (a[i].second.x - a[i].first.x + 1) * (a[i].second.y - a[i].first.y + 1) - spii);
}
yans += (sev(m_p(ban(0, 0), ban(n - 1, n - 1)), t) - g);
ans = min(ans, yans);
}
int b[8][8];
int main()
{
/*vv = true;
for (int i = 0; i < 6; ++i)
{
for (int j = 0; j < 6; ++j)
{
if (sevv(i, j, 1))
b[i][j] = 1;
}
}
for (int x1 = 0; x1 < 6; ++x1)
{
for (int x2 = x1; x2 < 6; ++x2)
{
for (int y1 = 0; y1 < 6; ++y1)
{
for (int y2 = y1; y2 < 6; ++y2)
{
cout << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << endl;
if (x1 == 4 && x2 == 4 && y1 == 0 && y2 == 4)
cout << "";
int ans1 = sev(m_p(ban(x1, y1), ban(x2, y2)), 1);
int ans2 = 0;
for (int i = x1; i <= x2; ++i)
{
for (int j = y1; j <= y2; ++j)
{
ans2 += b[i][j];
}
}
if (ans1 != ans2)
cout << "asdfdafjklshdfkjhaskjldfhakjl" << endl;
}
}
}
}*/
//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;
}
