#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point {
ll x, y;
// point(ll x, ll y) : x(x), y(y) {}
};
// returns number of black ceils on chess board a x b, f - color of first ceil (0 - white, 1 - black)
ll black_nums(ll a, ll b, bool f) {
if(a < 0 || b < 0) return 0;
if(f) return ((a + 1) / 2) * ((b + 1) / 2) + (a / 2) * (b / 2);
return (a / 2) * ((b + 1) / 2) + ((a + 1) / 2) * (b / 2);
}
ll func(point p1, point p2, ll d, bool cl) {
ll x1 = p1.x, x2 = p2.x, y1 = p1.y, y2 = p2.y;
ll dx1 = ((d - p1.x % d) % d);
ll dy1 = ((d - p1.y % d) % d);
ll dx2 = ((p2.x + 1) % d);
ll dy2 = ((p2.y + 1) % d);
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
if((dx1 || dx2) && p1.x / d == p2.x / d) dx1 = p2.x - p1.x + 1, dx2 = 0;
x1 += dx1; x2 -= dx2;
if((dx1 || dx2) && p1.y / d == p2.y / d) dy1 = p2.y - p1.y + 1, dy2 = 0;
y1 += dy1; y2 -= dy2;
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
// cout << dx1 << ' ' << dy1 << ' ' << dx2 << ' ' << dy2 << '\n';
ll cnt = 0;
cnt += black_nums((x2 - x1 + 1) / d, (y2 - y1 + 1) / d, (cl ^ ((x1 / d + y1 / d) % 2))) * d * d;
cnt += black_nums((x2 - x1 + 1) / d, 1, (cl ^ ((x1 / d + p1.y / d) % 2))) * dy1 * d;
cnt += black_nums((x2 - x1 + 1) / d, 1, (cl ^ ((x1 / d + p2.y / d) % 2))) * dy2 * d;
cnt += black_nums(1, (y2 - y1 + 1) / d, (cl ^ ((p1.x / d + y1 / d) % 2))) * dx1 * d;
cnt += black_nums(1, (y2 - y1 + 1) / d, (cl ^ ((p2.x / d + y1 / d) % 2))) * dx2 * d;
cnt += (cl ^ ((p1.x / d + p1.y / d) % 2)) * dx1 * dy1;
if(p2.x > p1.x) cnt += (cl ^ ((p2.x / d + p1.y / d) % 2)) * dx2 * dy1;
if(p2.y > p1.y) cnt += (cl ^ ((p1.x / d + p2.y / d) % 2)) * dx1 * dy2;
if(p2.x > p1.x && p2.y > p1.y) cnt += (cl ^ ((p2.x / d + p2.y / d) % 2)) * dx2 * dy2;
return cnt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll n, k;
cin >> n >> k;
vector<pair<point, point>> v;
for(int i = 1; i <= k; i++) {
point p1, p2;
cin >> p1.x >> p1.y;
p1.x--; p1.y--;
cin >> p2.x >> p2.y;
p2.x--; p2.y--;
v.push_back(make_pair(p1, p2));
}
ll ans = n * n;
for(ll D = 1; D * D <= n; D++) {
if(n % D) continue;
int d = D;
ll val = 0;
val = black_nums(n / d, n / d, 1) * d * d;
for(auto [p1, p2] : v) {
long long cnt = func(p1, p2, d, 1);
val += (p2.x - p1.x + 1) * (p2.y - p1.y + 1) - 2 * cnt;
}
ans = min(ans, val);
val = black_nums(n / d, n / d, 0) * d * d;
for(auto [p1, p2] : v) {
long long cnt = func(p1, p2, d, 0);
val += (p2.x - p1.x + 1) * (p2.y - p1.y + 1) - 2 * cnt;
}
ans = min(ans, val);
if(D == 1) continue;
d = n / D;
val = black_nums(n / d, n / d, 1) * d * d;
for(auto [p1, p2] : v) {
long long cnt = func(p1, p2, d, 1);
val += (p2.x - p1.x + 1) * (p2.y - p1.y + 1) - 2 * cnt;
}
ans = min(ans, val);
val = black_nums(n / d, n / d, 0) * d * d;
for(auto [p1, p2] : v) {
long long cnt = func(p1, p2, d, 0);
val += (p2.x - p1.x + 1) * (p2.y - p1.y + 1) - 2 * cnt;
}
ans = min(ans, val);
}
cout << ans;
}
