#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7;
const ll oo = 1e18;
signed main()
{
IO_OP;
int n, k;
cin >> n >> k;
V<array<int, 4>> a(k);
for(int i = 0; i < k; i++) {
for(int j = 0; j < 4; j++)
cin >> a[i][j], a[i][j]--;
}
ll ans = oo;
auto go = [&] (int b) {
assert(n % b == 0);
int m = n / b;
ll black = (ll) m * m / 2 * b * b, white = (ll) n * n - black;
int black_type = 1;
for(int _ = 0; _ < 2; _++) {
ll in_black = 0, in_white = 0;
for(int i = 0; i < k; i++) {
function<void(int, int, int, int)> solve = [&] (int x1, int y1, int x2, int y2) {
if(x1 > x2 || y1 > y2) return;
// int x1 = a[i][0], y1 = a[i][1];
// int x2 = a[i][2], y2 = a[i][3];
if(x1 / b == x2 / b && y1 / b == y2 / b) {
if((x1 + y1) % 2 == black_type)
in_black += (ll) (x2 - x1 + 1) * (y2 - y1 + 1);
else
in_white += (ll) (x2 - x1 + 1) * (y2 - y1 + 1);
} else if(y1 / b == y2 / b || x1 / b == x2 / b) {
if(y1 / b == y2 / b) {
swap(x1, y1);
swap(x2, y2);
}
int bl = y1 / b + 1;
int br = y2 / b - 1;
ll l_rem = (ll) (bl * b - y1) * (x2 - x1 + 1);
ll r_rem = (ll) (y2 - br * b) * (x2 - x1 + 1);
if((x1 / b + y1 / b) % 2 == black_type) in_black += l_rem;
else in_white += l_rem;
if((x2 / b + y2 / b) % 2 == black_type) in_black += r_rem;
else in_white += r_rem;
if((br - bl + 1) % 2 == 1) {
if((bl + x1 / b) % 2 == black_type)
in_black += (ll) b * (x2 - x1 + 1);
else
in_white += (ll) b * (x2 - x1 + 1);
}
} else {
int bl = y1 / b + 1, br = y2 / b - 1;
int bu = x1 / b + 1, bd = x2 / b - 1;
solve(x1, bl * b, bu * b - 1, br * b + b - 1);
solve(br * b + b, bl * b, x2, br * b + b - 1);
solve(bu * b, y1, bd * b + b - 1, bl * b - 1);
solve(bu * b, br * b + b, bd * b + b - 1, y2);
solve(x1, y1, bl * b - 1, br * b - 1);
solve(x1, br * b + b, bl * b - 1, y2);
solve(bd * b + b, y1, x2, bl * b - 1);
solve(bd * b + b, br * b + b, x2, y2);
if((br - bl + 1) % 2 == 1 && (bd - bu + 1) % 2 == 1) {
if((bl + bu) % 2 == black_type)
in_black += (ll) b * b;
else
in_white += (ll) b * b;
}
}
};
int x1 = a[i][0], y1 = a[i][1];
int x2 = a[i][2], y2 = a[i][3];
solve(x1, y1, x2, y2);
}
assert(in_black <= black);
assert(in_white <= white);
ans = min(ans, in_white + black - in_black);
swap(black, white);
black_type ^= 1;
}
};
for(int i = 1; i * i <= n; i++) {
if(n % i == 0) {
go(i);
if(n / i != i && n / i != n) go(n / i);
}
}
cout << ans << '\n';
}
