#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll n, k; vector<ll> v;
ll num[100100];
ll mod(ll x, ll vel){
if (x % vel == 0 && x != 0)
return vel;
return (x % vel);
}
bool black(ll x, ll y, ll vel){
x -= mod(x, vel); y -= mod(y, vel);
x /= vel; y /= vel;
if ((x + y) & 1)
return 0;
return 1;
}
ll pref(ll x, ll y, ll vel){
if (x == 0 || y == 0) return 0;
ll ans = 0;
ll x2 = x - mod(x, vel); ll y2 = y - mod(y, vel);
ll val1 = x2 / vel; ll val2 = y2 / vel;
ll p = val1 * val2; ll u = p / 2;
ans += -(p - u) * vel * vel + u * vel * vel;
p = val2; u = p / 2; ll pt = 1;
if (val1 % 2 == 0) pt = -1;
ans += pt * (p - u) * vel * (x - x2) + -pt * u * vel * (x - x2);
p = val1; u = p / 2; pt = 1;
if (val2 % 2 == 0) pt = -1;
ans += pt * (p - u) * vel * (y - y2) + -pt * u * vel * (y - y2);
if (black(x, y, vel))
ans -= (x - x2) * (y - y2);
else ans += (x - x2) * (y - y2);
return ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (ll i = 1; i < n; ++i){
if (n % i == 0){
v.push_back(i);
ll d = n / i;
num[i] = (d * d + 1) / 2; num[i] *= i * i;
}
}
for (int i = 0; i < k; ++i){
ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
for (ll vel: v){
num[vel] += (pref(x2, y2, vel) - pref(x2, y1 - 1, vel) - pref(x1 - 1, y2, vel) + pref(x1 - 1, y1 - 1, vel));
}
}
ll sol = 1e18;
for (ll x: v) sol = min(abs(sol), min(num[x], n * n - abs(num[x])));
cout << sol;
return 0;
}
