#include "bits/stdc++.h"
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
void solve(int tc) {
int n,k;
cin >> n>>k;
int x1[k],y1[k],x2[k],y2[k];
for(int i=0; i<k; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
x1[i]--; y1[i]--;
x2[i]--; y2[i]--;
}
vector<int> prof;
for(int i=1; i*i<=n; i++) {
if(n%i == 0) {
prof.push_back(i);
if(i*i!=n && i!=1) prof.push_back(n/i);
}
}
sort(prof.begin(), prof.end());
int ans = 1e18;
for(int s: prof) {
int c[2] = {0, 0}; // number of black cells for each (i/S + j/S) mod 2
for(int i=0; i<k; i++) {
int type0 = 0;
int type1 = 0;
int l = y1[i], r = y2[i];
if(l / (2*s) == r / (2*s)) {
if(r % (2*s) < s) type0 += r-l+1;
else if(l % (2*s) >= s) type0 += 0;
else type0 += s - (l % (2*s));
}
else {
if(l % (2*s) >= s) {
int md = l % (2*s);
l += 2*s - md;
}
else {
int md = l % (2*s);
type0 += s - md;
l += 2*s - md;
}
if(r % (2*s) >= s) {
int md = r % (2*s);
r -= md+1;
type0 += s;
}
else {
int md = r % (2*s);
r -= md+1;
type0 += md+1;
}
type0 += (r-l+1) / 2;
}
type1 = y2[i]-y1[i]+1 - type0;
l = x1[i], r = x2[i];
int type2 = 0;
int type3 = 0;
if(l / (2*s) == r / (2*s)) {
if(r % (2*s) < s) type2 += r-l+1;
else if(l % (2*s) >= s) type2 += 0;
else type2 += s - (l % (2*s));
}
else {
if(l % (2*s) >= s) {
int md = l % (2*s);
l += 2*s - md;
}
else {
int md = l % (2*s);
type2 += s - md;
l += 2*s - md;
}
if(r % (2*s) >= s) {
int md = r % (2*s);
r -= md+1;
type2 += s;
}
else {
int md = r % (2*s);
r -= md+1;
type2 += md+1;
}
type2 += (r-l+1) / 2;
}
type3 = x2[i]-x1[i]+1 - type2;
//cout<<s<<" "<<type0<<" "<<type1<<" "<<type2<<" "<<type3<<"\n";
int d = type0 * type2 + type1 * type3;
c[0] += d;
c[1] += (x2[i] - x1[i] + 1) * (y2[i] - y1[i] + 1) - d;
}
int t[2] = {0, 0};
int nums = (n/s) * (n/s);
t[0] = s*s * ((nums+1) / 2);
t[1] = s*s * (nums / 2);
ans = min(ans, abs(t[0] - c[0]) + c[1]);
ans = min(ans, abs(t[1] - c[1]) + c[0]);
// cout<<ans<<"\n";
}
cout << ans << "\n";
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t=1; //cin>>t;
for(int i=1; i<=t; i++)solve(i);
}
