#include <bits/stdc++.h>
#define N 100050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
ll n, k, x[N], y[N], xf[N], yf[N];
long long ans = (2000000000000000000ll);
vector<ll> d;
inline ll conta(ll x, ll y, ll r)
{
x ++, y ++;
ll tx = (x/r), ty = (y/r);
int rx = (tx % 2 == 0 ? 1 : 0), ry = (ty % 2 == 0 ? 1 : 0);
ll xo = ((tx + 1)/2)*r + (rx ? x % r : 0);
ll xi = (x - xo);
ll yo = ((ty + 1)/2)*r + (ry ? y % r : 0);
ll yi = (y - yo);
return xo*yo + xi*yi;
}
inline ll custo(ll xi, ll yi, ll xii, ll yii, ll r)
{
ll C = conta(xii, yii, r) - conta(xi - 1, yii, r) - conta(xii, yi - 1, r) + conta(xi - 1, yi - 1, r);
return C;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>k;
for(int i = 1; i <= k; i++) cin>>x[i]>>y[i]>>xf[i]>>yf[i];
for(int i = 1; i <= k; i++)
{
x[i] --, y[i] --, xf[i] --, yf[i] --;
if(x[i] > xf[i]) swap(x[i], xf[i]);
if(y[i] > yf[i]) swap(y[i], yf[i]);
}
for(int i = 1; i <= sqrt(n); i++)
{
if((n % i) != 0) continue;
d.push_back(i);
if(i != n/i) d.push_back(n/i);
}
for(auto r: d)
{
ll pretocerto = 0, pretoerrado = 0, tot;
if(r == n) continue;
tot = ( ((n/r) * (n/r)) + 1LL)/2LL;
tot = (tot * r * r);
for(int i = 1; i <= k; i++)
{
ll S = custo(x[i], y[i], xf[i], yf[i], r);
//cout<<"CUSTO "<<x[i]<<" "<<y[i]<<" "<<xf[i]<<" "<<yf[i]<<" = "<<S<<"\n";
pretocerto += S;
pretoerrado += (xf[i] - x[i] + 1) * (yf[i] - y[i] + 1) - S;
}
ans = min(ans, tot - pretocerto + pretoerrado);
tot = ( ((n/r) * (n/r)))/2LL;
tot = (tot * r * r);
ans = min(ans, tot + pretocerto - pretoerrado);
}
cout<<ans<<"\n";
}
