// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>
#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif
using namespace std ;
using ll = long long ;
bool isPrime(int x) {
if (x < 2) return 0 ;
for (int i = 2 ; i * i <= x ; i++) {
if (x % i == 0) {
return 0 ;
}
}
return 1 ;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(false) ;
ll n, k ; cin >> n >> k ;
if (isPrime(n)) {
vector<vector<int>> row(n + 1, vector<int>(2, 0)) ;
auto black = row , white = row ;
while (k--) {
int x1 , y1 , x2, y2 ;cin >> x1 >> y1 >> x2 >> y2 ;
row[x1][y1 % 2]++ ;
black[x1][y1 % 2]++ ;
}
int ret = 0 , sum = 0 ;
for (int i = 1 ; i <= n ; i++) {
if (i & 1) {
int len = (n + 1) / 2 ;
int cur = len - black[i][i % 2] + black[i][!(i % 2)] ;
sum += cur ;
} else {
int len = (n / 2) ;
int cur = len - black[i][i % 2] + black[i][!(i % 2)] ;
sum += cur ;
}
}
ret = sum ; sum = 0 ;
for (int i = 1 ; i <= n ; i++) {
if (i & 1) {
int len = (n) / 2 ;
int cur = len - black[i][!(i % 2)] + black[i][(i % 2)] ;
sum += cur ;
} else {
int len = ((n + 1) / 2) ;
int cur = len - black[i][!(i % 2)] + black[i][(i % 2)] ;
sum += cur ;
}
}
ret = min(ret, sum) ;
cout << ret ;
return 0 ;
}
vector<vector<int>> a(n + 2, vector<int>(n + 2, 0)) ;
auto b = a ;
for (int i = 0 ; i < k ; i++) {
int x1 , y1 , x2 , y2 ; cin >> x1 >> y1 >> x2 >> y2 ;
a[x1][y1]++ , a[x1][y2 + 1]-- ;
a[x2 + 1][y1]-- , a[x2 + 1][y2 + 1]++ ;
}
for (int i = 1 ; i <= n ; i++) {
for (int j = 1 ; j <= n ; j++) {
a[i][j] += a[i - 1][j] ;
a[i][j] += a[i][j - 1] ;
a[i][j] -= a[i - 1][j - 1] ;
a[i][j] = bool (a[i][j]) ;
b[i][j] = b[i - 1][j] + b[i][j - 1] + a[i][j] - b[i - 1][j - 1] ;
}
}
vector<int> d;
for (int i = 1 ; i * i <= n ; i++) {
if (n % i) continue ;
d.push_back(i) ;
if (n / i != i) d.push_back(n / i) ;
}
auto calc = [&](int len) -> int {
int N = n / len ;
vector<vector<vector<int>>> c(len + 3, vector<vector<int>>(len + 3, vector<int>(2 ,0))) ;
for (int i = 1 ; i <= n ; i++) {
for (int j = 1 ; j <= n ; j++) {
c[(i - 1) / N][(j - 1) / N][a[i][j]]++ ;
}
}
ll cur = 0 , ret = 0 ;
for (int i = 0 ; i < len ; i++) {
for (int j = 0 ; j < len ; j++) {
// dbg(i, j, c[i][j][0], c[i][j][1]) ;
if ((i % 2) != (j % 2)) {
ll sum = N * N - c[i][j][1] ;
cur += sum ;
} else {
ll sum = N * N - c[i][j][0] ;
cur += sum ;
}
}
}
ret = cur , cur = 0 ;
for (int i = 0 ; i < len ; i++) {
for (int j = 0 ; j < len ; j++) {
if ((i % 2) == (j % 2)) {
ll sum = N * N - c[i][j][1] ;
cur += sum ;
} else {
ll sum = N * N - c[i][j][0] ;
cur += sum ;
}
}
}
ret = min(ret, cur) ;
return ret ;
};
sort(d.begin(), d.end()) ;
int ret = INT_MAX ;
for (int i : d) {
if (i > 1) {
dbg(i, calc(i)) ;
ret = min(ret, calc(i)) ;
}
}
cout << ret ;
return 0 ;
}
// 希望白银
