#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};
ll n,k;
vector<ll> v[N+1];
int cunt=0;
ll calc(bool state,ll d){
ll res=0,ok=state;
for(int x = 1; x <= n; x++){
ll cur=d,ok2=ok,i=0;
while(i<v[x].sz){
ll j=i,cnt=0;
while(j<v[x].sz && v[x][j]<=cur){
cnt++;
j++;
cunt++;
}
if(ok2) res+=d-cnt;
else res+=cnt;
ok2^=1;
cur+=d;
i=j;
}
if(cur<=n){
cur-=d;
ll p=(n-cur)/d;
if(ok2)
p=(p+1)/2;
else
p/=2;
p*=d;
res+=p;
}
if(x%d==0){
ok^=1;
}
}
assert(cunt<=k);
// cout<<d<<" "<<cunt<<"\n";
cunt=0;
return res;
}
void solve() {
cin>>n>>k;
for(int i = 1; i <= k; i++){
ll x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
v[x1].pb(y1);
}
/*
int u=0;
for(int i = 1; i <= n && u<k; i++){
for(int j = 1; j <= n && u<k; j++){
v[i].pb(j);
u++;
}
}
*/
for(int i = 1; i <= n; i++){
sort(all(v[i]));
}
vector<ll> 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);
}
}
sort(all(D));
ll ans=INF;
for(auto d: D){
//cout<<d<<" "<<calc(0,d)<<" "<<calc(1,d)<<"\n";
ans=min(ans,calc(0,d));
ans=min(ans,calc(1,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;
}
