#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define pb push_back #define all(x) x.begin() x.end() #define MOD (1e9+7) const int N = 1e6; int n, k; vector<vector<bool>> v; void solve(){ cin >> n >> k; int a = 0; for(int i = 1; i <= sqrt(n); ++i){ if(n % i == 0) a++; } if(a == 1){ int c1 = 0, c2 = 0; for(int i = 0; i < k; ++i){ int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; int val = x1-1+y1-1; if(val%2) c1++; else c2++; } cout << min(c1 + ll(n)*n/2 + 1 - c2, c2 + ll(n)*n/2 - c1); return; } v.resize(n); for(int i = 0; i < n; ++i) v[i].resize(n); for(int i = 0; i < k; ++i){ int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; v[x1 - 1][y1 - 1] = 1; } int ans = MOD; for(int i = 1; i < n; ++i){ if(n % i == 0){ for(int rep = 0; rep < 2; ++rep){ int c = 0; for(int jx = 0; jx < n; ++jx){ for(int jy = 0; jy < n; ++jy){ int val = jx/i + jy/i; c += (val%2)^rep^v[jx][jy]; } } ans = min(ans, c); } } } cout << ans; } int main(){ solve(); return 0; }