#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define pb push_back
#define pii pair<int,int>
#define sz size()
#define all(v) v.begin(),v.end()
#define fi first
#define se second
const int N = 1e5;
const int mod = 1e9+7;
const ll INF = 1e18;
const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};
int n,k;
vector<pii> v;
ll calc(int ok,int d){
ll res=((n/d)*(n/d)+1)/2;
res*=d*d;
for(auto [X,Y]: v){
int x=(X+d-1)/d;
int y=(Y+d-1)/d;
if(x%2==ok){
if(y%2==ok)
res--;
else
res++;
}
else{
if(y%2==ok)
res++;
else
res--;
}
}
return res;
}
void solve() {
cin>>n>>k;
for(int i = 1; i <= k; i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
v.pb({x1,y1});
}
vector<int> D;
for(ll i = 1; i*i <= n; i++){
if(n%i==0){
D.pb(i);
if(i*i!=n && i!=1)
D.pb(n/i);
}
}
ll ans=INF;
for(auto d: D){
ans=min(ans,calc(1,d));
ans=min(ans,calc(0,d));
}
cout<<ans<<"\n";
}
int main() {
//freopen("cowrun.in","r",stdin);
//freopen("cowrun.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1;
//cin>>t;
while(t--) {
solve();
}
return 0;
}
