#include <bits/stdc++.h>
using namespace std;
#define x1 x1_
#define x2 x2_
#define y1 y1_
#define y2 y2_
const int N = 1e5 + 5;
const int BLACK_FIRST = 0;
const int WHITE_FIRST = 1;
// color of a ceil will be determined by (id row + id col) % 2 and the color of first block (BLACK_FIRST / WHITE_FIRST)
// in particular: (id row + id col) % 2 = BLACK_FIRST --> black id, otherwise ...
// id row = row div edge
int n, k;
int x[2][N], y[2][N];
void read() {
cin >> n >> k;
for (int i = 1; i <= k; i++) {
for (int j = 0; j < 2; j++) {
cin >> x[j][i] >> y[j][i];
--x[j][i];
--y[j][i];
}
}
}
int id_block (int x, int edge) {
return x / edge;
}
// (0...x1) / k % 2 == type
int num_ceil (int x, int k, int type) {
if (x < 0) {
return 0;
}
if (x == 0) {
return (x / k) % 2 == type;
}
int block_x = id_block(x, k);
int ans = 0;
if (block_x > 0) {
// [0, block_x - 1]
if (type == 0) {
ans += (block_x - block_x / 2) * k;
}
else {
ans += (block_x / 2) * k;
}
}
// just in block_x
int lo = block_x * k;
int hi = x;
if (block_x % 2 == type) {
ans += (hi - lo + 1);
}
return ans;
}
int num_ceil (int l, int r, int k, int type) {
assert(num_ceil(r, k, type) >= num_ceil(l - 1, k, type));
return num_ceil(r, k, type) - num_ceil(l - 1, k, type);
}
int64_t solve (int edge, int type) {
int64_t ans = 0;
// (r + c) % 2 == type
for (int row_type = 0; row_type < 2; row_type++) {
int col_type = (type - row_type + 2) % 2;
ans += 1ll * num_ceil(0, n - 1, edge, row_type) * num_ceil(0, n - 1, edge, col_type);
}
for (int i = 1; i <= k; i++) {
for (int row_type = 0; row_type < 2; row_type++) {
for (int col_type = 0; col_type < 2; col_type++) {
// already black
// since we colored it before --> subtract
if ((row_type + col_type) % 2 == type) {
ans -= 1ll * num_ceil(x[0][i], x[1][i], edge, row_type) * num_ceil(y[0][i], y[1][i], edge, col_type);
}
// must be white, but now it's black
else {
ans += 1ll * num_ceil(x[0][i], x[1][i], edge, row_type) * num_ceil(y[0][i], y[1][i], edge, col_type);
}
}
}
}
return ans;
}
void solve() {
int64_t best = 9e18;
for (int edge = 1; edge < n; edge++) {
if (n % edge) {
continue;
}
best = min(best, solve(edge, BLACK_FIRST));
best = min(best, solve(edge, WHITE_FIRST));
}
cout << best;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
read();
solve();
return 0;
}
