#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
const int INF=1000000000000000000;
//const int INF=1e9;
const int N=200000;
const int M=998244353;
const int ln=20;
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
return os << p.fi << "," << p.se << " ";
}
struct segtree{
vector<pii> seg;
vector<int> lazy;
segtree(int n){
for(int i=0;i<4*n;i++){
seg.push_back(mp(0,0));
lazy.push_back(0);
}
}
void Build(int l,int r,int pos){
if(l==r){
seg[pos]=mp(l,-l);
lazy[pos]=0;
return;
}
int m=(l+r)/2;
Build(l,m,2*pos);
Build(m+1,r,2*pos+1);
seg[pos]=min(seg[2*pos],seg[2*pos+1]);
}
void UpdateLazy(int l,int r,int pos){
if(lazy[pos]==0) return;
seg[pos].fi+=lazy[pos];
if(l!=r){
lazy[2*pos]+=lazy[pos];
lazy[2*pos+1]+=lazy[pos];
}
lazy[pos]=0;
}
void Update(int l,int r,int pos,int ql,int qr,int val){
UpdateLazy(l,r,pos);
if(ql>r || qr<l) return;
if(ql<=l && qr>=r){
lazy[pos]+=val;
UpdateLazy(l,r,pos);
return;
}
int m=(l+r)/2;
Update(l,m,2*pos,ql,qr,val);
Update(m+1,r,2*pos+1,ql,qr,val);
seg[pos]=min(seg[2*pos],seg[2*pos+1]);
}
pii Query(int l,int r,int pos,int ql,int qr){
UpdateLazy(l,r,pos);
if(ql>r || qr<l) return mp(INF,INF);
if(ql<=l && qr>=r){
return seg[pos];
}
int m=(l+r)/2;
return min(Query(l,m,2*pos,ql,qr),Query(m+1,r,2*pos+1,ql,qr));
}
};
int f[N+1];
void solve(){
int n,k;
cin >> n >> k;
vector<int> div;
for(int i=1;i<n;i++){
if(n%i==0) div.push_back(i);
}
pii pos[k];
for(int i=0;i<k;i++){
int xi,yi;
int xj,yj;
cin >> xi >> yi >> xj >> yj;
xi--,yi--,xj--,yj--;
assert(xi==xj && yi==yj);
pos[i]=mp(xi,yi);
}
int mn=INF;
for(int d:div){
for(int cs=0;cs<2;cs++){
int os;
if((n/d)%2!=0){
if(cs==0) os=(n*n+d*d)/2;
else os=(n*n-d*d)/2;
} else{
os=(n*n)/2;
}
for(int i=0;i<k;i++){
int i1=pos[i].fi/d;
int i2=pos[i].se/d;
if((i1+i2)%2==cs){
os--;
} else os++;
}
mn=min(mn,os);
}
}
cout << mn << "\n";
}
signed main(){
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t;
//cin >> t;
t=1;
while(t--) solve();
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
}
