#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e5 + 5;
ll n, k;
ll x[N], y[N], X[N], Y[N];
ll a[2][2];
ll S1, S2;
ll ans;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>k;
for (ll i = 1; i <= k; i++){
cin>>x[i]>>y[i]>>X[i]>>Y[i];
x[i]--;
y[i]--;
X[i]--;
Y[i]--;
S1 += (X[i] - x[i] + 1) * (Y[i] - y[i] + 1);
}
S2 = n * n - S1;
ans = n * n;
for (ll I = 1; I < n; I++)
if (n % I == 0){
ll s1 = ((n / I) * (n / I) + 1) / 2 * I * I, s2 = (n / I) * (n / I) / 2 * I * I;
ll m1 = 0, m2 = 0;
for (ll i = 1; i <= k; i++){
for (ll j = 0; j < 2; j++)
for (ll l = 0; l < 2; l++)
a[j][l] = 0;
ll p, q, t;
p = (x[i] + I - 1) / I * I;
if (X[i] < p)
a[0][(x[i] / I) % 2] += X[i] - x[i] + 1;
else {
q = X[i] / I * I;
t = (q - p) / I;
a[0][(x[i] / I) % 2] += p - x[i];
a[0][(X[i] / I) % 2] += X[i] - q + 1;
a[0][(p / I) % 2] += (t + 1) / 2 * I;
a[0][(p / I + 1) % 2] += t / 2 * I;
}
p = (y[i] + I - 1) / I * I;
if (Y[i] < p)
a[1][(y[i] / I) % 2] += Y[i] - y[i] + 1;
else {
q = Y[i] / I * I;
t = (q - p) / I;
a[1][(y[i] / I) % 2] += p - y[i];
a[1][(Y[i] / I) % 2] += Y[i] - q + 1;
a[1][(p / I) % 2] += (t + 1) / 2 * I;
a[1][(p / I + 1) % 2] += t / 2 * I;
}
m1 += a[0][0] * a[1][0] + a[0][1] * a[1][1];
m2 += a[0][0] * a[1][1] + a[0][1] * a[1][0];
}
ll pas = 0;
pas = n * n - m1 - (s2 - m2);
ans = min (ans, pas);
pas = n * n - m2 - (s1 - m1);
ans = min (ans, pas);
}
cout<<ans<<endl;
return 0;
}
