#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
vector<ll> divs(ll x)
{
vector<ll> ans;
for (ll y = 1; y*y <= x; ++y) {
if (x%y == 0) {
ans.push_back(y);
ans.push_back(x/y);
}
}
return ans;
}
pll get(ll l, ll r, ll len)
{
ll len2 = len*2;
ll l2 = l%len2? l-l%len2+len2: l;
ll r2 = r%len2? r-r%len2: r;
ll a0 = (r2-l2)/2;
ll a1 = (r2-l2)/2;
a0 += max(0ll, l2-l-len);
a1 += min(len, l2-l);
a0 += min(len, r-r2);
a1 += max(0ll, r-r2-len);
return {a0, a1};
}
const int N = 100'010;
ll l0[N], r0[N];
ll l1[N], r1[N];
int main()
{
cin.tie(0) -> sync_with_stdio(false);
ll n, k;
cin >> n >> k;
Loop (i,0,k) {
cin >> l0[i] >> l1[i];
cin >> r0[i] >> r1[i];
--l0[i]; --l1[i];
}
ll ans = n*n;
for (ll x : divs(n)) {
if (x == n)
continue;
ll sm0 = ((n/x) * (n/x) + 1)/2 * x * x;
ll sm1 = ((n/x) * (n/x))/2 * x * x;
Loop (i,0,k) {
auto [a0, a1] = get(l0[i], r0[i], x);
auto [b0, b1] = get(l1[i], r1[i], x);
ll bl0 = a0*b0 + a1*b1;
ll bl1 = a0*b1 + a1*b0;
sm0 -= bl0;
sm1 -= bl1;
sm0 += (r0[i] - l0[i]) * (r1[i] - l1[i]) - bl0;
sm1 += (r0[i] - l0[i]) * (r1[i] - l1[i]) - bl1;
}
ans = min(ans, sm0);
ans = min(ans, sm1);
}
cout << ans << '\n';
}
