#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
int n, k;
pii p[N], q[N];
vector <ll> v;
ll ans = 1e18;
int main () {
// freopen ("input.txt", "r", stdin);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
for (int i = 1; i < n; ++i) {
if (n % i == 0) {
v.pb (i);
}
}
for (int i = 1; i <= k; ++i) {
cin >> p[i].ff >> p[i].ss >> q[i].ff >> q[i].ss;
assert (p[i].ff == q[i].ff);
assert (p[i].ss == q[i].ss);
}
for (ll bol : v) {
// 1-nji ak bolsa
ll jogap = 0, ak = 0;
ll opyshy_gara = (((n / bol) * (n / bol)) / 2) * bol * bol;
for (int i = 1; i <= k; ++i) {
int a1 = (p[i].ff + bol - 1) / bol, b1 = (p[i].ss + bol - 1) / bol;
if (a1 % 2 == b1 % 2) {
ak++;
}
}
jogap = (opyshy_gara - k) + (ak * 2LL);
// indi gara etyas
ak = 0;
opyshy_gara = ((((n / bol) * (n / bol)) + 1) / 2) * bol * bol;
for (int i = 1; i <= k; ++i) {
int a1 = (p[i].ff + bol - 1) / bol, b1 = (p[i].ss + bol - 1) / bol;
if ((a1 % 2 == 1 and b1 % 2 == 0) or (a1 % 2 == 0 and b1 % 2 == 1)) {
ak++;
}
}
ll jogap1 = (opyshy_gara - k) + (ak * 2LL);
ans = min ({ans, jogap, jogap1});
}
cout << ans << "\n";
}
