#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ff first
#define ss second
#define Maxn 100009
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
#define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> order;
int n, k;
pii x[Maxn];
pii y[Maxn];
ll ans = llInf;
vector <int> A;
bool calc (int x, int y, int z) {
x --, y --;
return ((x / z) % 2) ^ ((y / z) % 2);
}
int main () {
//freopen ("file.in", "r", stdin);
//freopen ("file.out", "w", stdout);
//srand ((unsigned) time ( NULL ));
//int randomNumber = rand() % 10 + 1;
scanf ("%d%d", &n, &k);
for (int i = 1; i <= k; i++)
scanf ("%d%d%d%d", &x[i].ff, &y[i].ff, &x[i].ss, &y[i].ss);
for (int i = 1; i < n; i++)
if (!(n % i))
A.pb (i);
for (auto j: A) {
ll v = j;
ll u = n / j;
ll sm1[2], sm2[2];
sm1[0] = sm2[1] = 0;
sm1[1] = (((u * u) + 1) / 2) * v * v;
sm2[0] = ((u * u) / 2) * v * v;
for (int i = 1; i <= k; i++) {
ll a = min ((j - (x[i].ff - 1) % j) % j, x[i].ss - x[i].ff + 1);
ll b = x[i].ss % j;
ll c = min ((j - (y[i].ff - 1) % j) % j, y[i].ss - y[i].ff + 1);
ll d = y[i].ss % j;
if (x[i].ff + a > x[i].ss)
b = 0;
if (y[i].ff + c > y[i].ss)
d = 0;
bool e = calc (x[i].ff, y[i].ff, j);
sm1[e] += a * c, sm2[e] += a * c;
e = calc (x[i].ff, y[i].ff + c, j);
ll t = (y[i].ss - y[i].ff - c + 1) / j;
ll r = (t + 1) / 2 * a * j;
sm1[e] += r, sm2[e] += r;
r = t / 2 * a * j;
sm1[!e] += r, sm2[!e] += r;
e = calc (x[i].ff, y[i].ss, j);
sm1[e] += a * d, sm2[e] += a * d;
ll xx1 = x[i].ff + a;
if (xx1 > x[i].ss)
continue;
e = calc (x[i].ss, y[i].ff, j);
sm1[e] += b * c, sm2[e] += b * c;
e = calc (x[i].ss, y[i].ff + c, j);
r = (t + 1) / 2 * b * j;
sm1[e] += r, sm2[e] += r;
r = t / 2 * b * j;
sm1[!e] += r, sm2[!e] += r;
e = calc (x[i].ss, y[i].ss, j);
sm1[e] += b * d, sm2[e] += b * d;
ll xx2 = x[i].ss - b;
if (xx1 > xx2)
continue;
e = calc (xx1, y[i].ff, j);
t = (xx2 - xx1 + 1) / j;
r = (t + 1) / 2 * c * j;
sm1[e] += r, sm2[e] += r;
r = t / 2 * c * j;
sm1[!e] += r, sm2[!e] += r;
ll yy1 = y[i].ff + c;
if (yy1 > y[i].ss)
continue;
e = calc (xx1, y[i].ss, j);
r = (t + 1) / 2 * d * j;
sm1[e] += r, sm2[e] += r;
r = t / 2 * d * j;
sm1[!e] += r, sm2[!e] += r;
ll yy2 = y[i].ss - d;
if (yy1 > yy2)
continue;
e = calc (xx1, yy1, j);
t = (yy2 - yy1 + 1) / j;
ll t1 = (xx2 - xx1 + 1) / j;
r = (((t + 1) / 2) * ((t1 + 1) / 2) + (t / 2) * (t1 / 2)) * j * j;
sm1[e] += r, sm2[e] += r;
r = ((t / 2) * ((t1 + 1) / 2) + ((t + 1) / 2) * (t1 / 2)) * j * j;
sm1[!e] += r, sm2[!e] += r;
}
ans = min (ans, min (sm1[1] - sm1[0], sm2[0] - sm2[1]));
}
printf ("%lld\n", ans);
return 0;
}
