#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;
if (k == 0) {
int ans = -1;
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
int m = n / i;
int res = ((n * n) / (m * m)) / 2 * (m * m);
if (ans == -1 || ans > res)
ans = res;
}
}
cout << ans << '\n';
return 0;
}
bool ok = true;
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];
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;
}
if (ok && n <= 1000) {
vector <vector <int> > mas(n,vector <int> (n, 0));
}
return 0;
}
