#include <bits/stdc++.h>
#define pb push_back
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N = 1e5 + 5;
ll n, m, ans = INF;
vector <int> divs;
ll dp[N];
void add(int num) {
if (num == n) return;
divs.pb(num);
ll len = n / num;
dp[num] = (len * len + 1) / 2 * num * num;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n >> m;
for (int i = 1; i * i <= n; i++) {
if (n % i != 0) continue;
add(i);
if (i * i != n) add(n / i);
}
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b >> a >> b;
// cout << a << " " << b << ": ";
for (auto& num : divs) {
int col = ((a + num - 1) / num + (b + num - 1) / num)&1; // 0 ? black : white
// cout << num << ',' << col << ' ';
dp[num] += col == 1 ? 1 : -1;
}
// cout << '\n';
}
for (auto& num : divs) {
// cout << num << ": " << dp[num] << '\n';
ans = min(ans, min(dp[num], n * n - dp[num]));
}
cout << ans << '\n';
}
