#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e5;
vector<int> g[N+1];
int odd[N+1], even[N+1];
int n, k;
int dp[1001][1001];
int isprime(int n){
for(int i =2; i * i <= n; i++){
if(n%i==0) return 0;
}
return 1;
}
int get(int x, int y, int x1, int y1){
return dp[x1][y1] - dp[x-1][y1] - dp[x1][y-1]+dp[x-1][y-1];
}
/*
6 8
1 3 1 3
1 4 1 4
2 3 2 3
2 4 2 4
3 1 3 1
3 2 3 2
4 1 4 1
4 2 4 2
*/
main(){
cin >> n >> k;
int Pr = isprime(n);
int x[k], y[k], x1[k], y1[k];
for(int i = 0;i < k; i++){
cin >> x[i] >> y[i] >> x1[i] >> y1[i];
if(Pr==0) dp[x[i]][y[i]] = 1;
odd[x[i]] += (y[i]%2==1);
even[x[i]]+= (y[i]%2==0);
}
int answer = INT_MAX;
// if(k == 0){
// for(int i = 1;i * i < n*n; i++){
// if(n%i==0){
// int j = n / i, black = 0;
// for(int c = 1; c <= j; c++){
// if(c%2==1){
// black+= (j / 2) * (i*i);
// }else{
// black+= (j-(j / 2))*(i*i);
// }
// }
// answer = min(answer, black);
// }
// }
// cout << answer;
// return 0;
// }
if(Pr){
int S = 0, S1 = 0;
for(int i = 1;i <= n; i++){
if(i%2==1){
S+= even[i];
S+= ((n+1)/2) - odd[i];
}else{
S+= odd[i];
S+= (n / 2)-even[i];
}
}
for(int i = 1;i <= n; i++){
if(i%2==1){
S1+= odd[i];
S1+= (n / 2)-even[i];
}else{
S1+= even[i];
S1+= ((n+1)/2) - odd[i];
}
}
cout << min(S, S1);
return 0;
}
// cout << "THE matrix is " << '\n';
// for(int i = 1;i <= n; i++){
// for(int j = 1;j <= n; j++) cout << dp[i][j] << ' ';
// cout << '\n';
// }
// cout << '\n' << '\n';
for(int i = 1;i <= n; i++){
for(int j = 1;j <= n; j++){
dp[i][j]+= dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
}
}
for(int i = 1;i * i < n*n; i++){
if(n%i==0){
int j = n / i, need = 0;
int col = 1, row = 1;
for(int c = 1; c <= j; c++, row+= i, col = 1){
if(c%2==1){
for(int r = 1; r <= j; r++, col+= i){
if(row + i-1 > n or col+i-1 > n) assert(false);
int black = get(row, col ,row+i-1, col+i-1);
// if(i ==2)
// cout << row << ' ' << col << " = " << black << '\n';
int white = i*i - black;
if(r%2==1){
need+= black;
}else{
need+= white;
}
}
}else{
for(int r = 1; r <= j; r++, col+= i){
if(row + i-1 > n or col+i-1 > n) assert(false);
int black = get(row, col ,row+i-1, col+i-1);
// if(i == 2)
// cout << row << ' ' << col << " = " << black << '\n';
int white = i*i - black;
if(r%2==0){
need+= black;
}else{
need+= white;
}
}
}
}
// if(need == 14) cout << i << '\n';
answer = min(answer, need);
need = 0, col = 1, row = 1;
for(int c = 1; c <= j; c++, row+= i, col = 1){
if(c%2==0){
for(int r = 1; r <= j; r++, col+= i){
if(row + i-1 > n or col+i-1 > n) assert(false);
int black = get(row, col ,row+i-1, col+i-1);
int white = i*i - black;
if(r%2==1){
need+= black;
}else{
need+= white;
}
}
}else{
for(int r = 1; r <= j; r++, col+= i){
if(row + i-1 > n or col+i-1 > n) assert(false);
int black = get(row, col ,row+i-1, col+i-1);
int white = i*i - black;
if(r%2==0){
need+= black;
}else{
need+= white;
}
}
}
}
answer = min(answer, need);
}
}
cout << answer;
return 0;
}
