#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
// ilość pełnych pól
int proper(int x, int y) {
return x/2 * y + (x%2 ? y/2 : 0);
}
int bottom(int x, int y, int r) {
if(x/r % 2 == 1) {
return
(x%r+1) * ((y/r+1)/2) * r;
} else {
return
(x%r+1) * (y/r/2) * r;
}
}
int side(int x, int y, int r) {
if(y/r%2 == 1) {
return (y%r+1) * ((x/r+1)/2) * r;
} else {
return (y%r+1) * (x/r/2) * r;
}
}
// ilość czarnych w rogu
int corner(int x, int y, int r) {
if(x < 0 || y < 0) return 0;
int total = proper(x/r, y/r) * r * r;
// cerr << total << "\n";
total += bottom(x, y, r);
// cerr << total << "\n";
total += side(x, y, r);
// cerr << total << "\n";
if((x/r + y/r) % 2 == 1)
total += (x%r+1) * (y%r+1);
return total;
}
// ilośc czarnych w prostokącie
int rectangle(int x1, int y1, int x2, int y2, int r) {
return corner(x2, y2, r) - corner(x1 - 1, y2, r) - corner(x2, y1 - 1, r) +
corner(x1 - 1, y1 - 1, r);
}
vector<tuple<int, int, int, int>> rec;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// int x, y;
// cin >> x >> y;
// cout << corner(x, y, 2) << "\n";
// return 0;
int n, k;
cin >> n >> k;
for(int i=0;i<k;i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--, y1--, x2--, y2--;
rec.pb({x1, y1, x2, y2});
}
int ans = n*n;
for(int r=1;r<n;r++) {
if(n%r) continue;
cerr << "---" << r << "---" << "\n";
int white_corner = (r*r) * ((n/r)*(n/r) / 2);
int black_corner = (r*r) * (((n/r)*(n/r)+1) / 2);
for(auto [x1, y1, x2, y2] : rec) {
int squares = rectangle(x1, y1, x2, y2, r);
int total = (x2-x1+1) * (y2-y1+1);
white_corner -= squares;
white_corner += total-squares;
cerr << squares << " " << total-squares << "\n";
black_corner -= total-squares;
black_corner += squares;
}
cerr << r << " " << white_corner << " " << black_corner << "\n";
ans = min({ans, white_corner, black_corner});
}
cout << ans << "\n";
}
