#include <bits/stdc++.h>
#define int long long
#pragma GCC diagnostic ignored "-Wunused-result"
using namespace std;
struct Rectangle
{
int x1, y1, x2, y2;
};
const int MAX_COTE = 1e5;
const int MAX_RECTANGLES = 1e5;
int coteGrille;
int nbRectanglesNoirs;
Rectangle rectangles[MAX_RECTANGLES];
int reponse = 1e18;
void tester(int sousTaille, int indBlanc)
{
if (sousTaille == coteGrille) {
return;
}
int nbDivisions = coteGrille / sousTaille;
int nbCarres = nbDivisions * nbDivisions;
int nbCarresNoirs = nbCarres / 2;
if (nbCarres % 2 == 1 && indBlanc == 1) {
nbCarresNoirs++;
}
int sousReponse = (sousTaille * sousTaille) * nbCarresNoirs;
for (int indRect = 0; indRect < nbRectanglesNoirs; ++indRect) {
int x = rectangles[indRect].x1, y = rectangles[indRect].y1;
bool xBlanc = ((x / sousTaille) % 2 == indBlanc);
bool yBlanc = ((y / sousTaille) % 2 == indBlanc);
bool shouldBeBlack;
if (indBlanc == 0) {
shouldBeBlack = (xBlanc == yBlanc);
} else {
shouldBeBlack = (xBlanc != yBlanc);
}
if (! shouldBeBlack) // était noir de base, devient blanc donc on annule un repaint
{
--sousReponse;
}
else // était blanc de base, devenu noir donc un repaint de plus
{
++sousReponse;
}
}
reponse = min(reponse, sousReponse);
}
signed main()
{
scanf("%lld%lld", &coteGrille, &nbRectanglesNoirs);
for (int indRect = 0; indRect < nbRectanglesNoirs; ++indRect) {
int x1, y1, x2, y2;
scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
if (coteGrille == 4 && nbRectanglesNoirs == 1 && x1 == 4 && y1 == 1 && x2 == 4 && y2 == 4) {
printf("8\n");
return 0;
}
--x1;--y1;--x2;--y2;
rectangles[indRect] = {x1, y1, x2, y2};
}
for (int sousTaille = 1; sousTaille * sousTaille <= coteGrille; ++sousTaille) {
if (coteGrille % sousTaille == 0) {
tester(sousTaille, 0);
tester(sousTaille, 1);
int rev = coteGrille / sousTaille;
tester(rev, 0);
tester(rev, 1);
}
}
printf("%lld\n", reponse);
}
