#include <bits/stdc++.h>
using namespace std;
#define int long long
int isprime(int n) {
if (n == 2) return false;
for (int i = 2; i < n; i++) {
if (n % i == 0) return false;
}
return true;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector <int> x1(k), x2(k), y1(k), y2(k);
for (int i = 0; i < k; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
}
// subtest1
if (k == 0) {
int ans = -1;
for (int i = 1; i < n; i++) {
if (n % i == 0) {
int res = ((n * n) / (i * i)) / 2 * (i * i);
if (ans == -1 || ans > res)
ans = res;
}
}
cout << ans << '\n';
return 0;
}
/// subtest2
bool ok = true;
for (int i = 0; i < k; i++) {
if (x1[i] != x2[i] || y1[i] != y2[i])
ok = false;
}
if (ok && isprime(n)) {
int cnt[] = {0, 0};
for (int i = 0, x, y; i < k; i++) {
x = x1[i]; y = y1[i];
cnt[(x + y) % 2]++;
}
if (n == 2) {
cout << min(2 - cnt[0] + cnt[1], 2 - cnt[1] + cnt[0]);
} else {
cout << min(n * n / 2 + 1 - cnt[0] + cnt[1], n * n / 2 - cnt[1] + cnt[0]);
}
return 0;
}
// stupid //subtest3, subtes4
if (n <= 0) {
cerr << "3, 4" << '\n';
vector <vector <int> > sum(1+n,vector <int> (1+n, 0));
for (int i = 0; i < k; i++) {
for (int x = x1[i]; x <= x2[i]; x++)
for (int y = y1[i]; y <= y2[i]; y++)
sum[x][y] = 1;
}
//for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// cout << sum[i][j] << ' ';
// }
// cout << '\n';
//}
//cout << '\n';
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] += sum[i][j-1];
sum[i][j] += sum[i-1][j];
sum[i][j] -= sum[i-1][j-1];
}
}
//for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// cout << sum[i][j] << ' ';
// }
// cout << '\n';
//}
//cout << '\n';
vector <int> div;
for (int i = 1; i < n; i++)
if (n % i == 0)
div.push_back(i);
int ans = 9e18;
for (auto D: div) {
int cnt[] = {0, 0};
int pos = 1;
for (int i = 1;; i += D) {
if (i + D - 1 > n) break;
int par = (pos & 1);
for (int j = 1;; j += D) {
if (j + D - 1 > n) break;
int i2 = i + D - 1, j2 = j + D - 1;
int A = sum[i2][j2];
A -= sum[i2][j-1];
A -= sum[i-1][j2];
A += sum[i-1][j-1];
cnt[par] += A;
par ^= 1;
}
pos++;
}
//cout << D << ' ' << cnt[1] << ' ' << cnt[0] << '\n';
int sc = ((n*n)/(D*D))/2*(D*D);
int fr = ((n*n)/(D*D)+1)/2*(D*D);
//cout << min({fr-cnt[1]+cnt[0],sc-cnt[0]+cnt[1]}) << '\n';
ans = min({ans, fr-cnt[1]+cnt[0], sc-cnt[0]+cnt[1]});
}
cout << ans << '\n';
} else if (n <= 100000) {
cerr << "5" << '\n';
vector <int> div;
for (int i = 1; i < n; i++)
if (n % i == 0)
div.push_back(i);
int ans = n * n;
for (auto D: div) {
int cnt[] = {0, 0};
for (int i = 0; i < k; i++) {
int x = (x1[i] + D - 1) / D, y = (y1[i] + D - 1) / D;
if (x % 2 == y % 2) {
cnt[1] ++;
} else {
cnt[0] ++;
}
}
//cout << D << ' ' << cnt[1] << ' ' << cnt[0] << '\n';
int sc = ((n*n)/(D*D))/2*(D*D);
int fr = ((n*n)/(D*D)+1)/2*(D*D);
//cout << min({fr-cnt[1]+cnt[0],sc-cnt[0]+cnt[1]}) << '\n';
ans = min({ans, fr-cnt[1]+cnt[0], sc-cnt[0]+cnt[1]});
}
cout << ans << '\n';
}
return 0;
}
