#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <cmath>
#include <unordered_map>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
const ll INF = 1e18;
struct Rectangle {
ll x1, y1, x2, y2;
Rectangle(ll x1_, ll y1_, ll x2_, ll y2_) :x1(x1_), y1(y1_), x2(x2_), y2(y2_) {}
ll area() const {
return (x2 - x1 + 1) * (y2 - y1 + 1);
}
};
//0 - white, 1 - black
ll paint(ll d, ll n, const Rectangle& r) {
ll dim1 = r.x2 - r.x1 + 1, dim2 = r.y2 - r.y1 + 1;
ll ans = 0;
ll xr1 = r.x1 / d, yr1 = r.y1 / d;
ll xr2 = r.x2 / d, yr2 = r.y2 / d;
ll xfull1 = xr1 + 1, yfull1 = yr1 + 1;
ll xfull2 = xr2 - 1, yfull2 = yr2 - 1;
if (xfull1 <= xfull2 && yfull1 <= yfull2) {
ll color = (xfull1 + yfull1) % 2;
ll d1 = (xfull2 - xfull1 + 1), d2 = (yfull2 - yfull1 + 1);
if (d1 % 2 == 1 && d2 % 2 == 1) {
ans += ((d1 * d2) / 2 + (color == 0)) * (d * d);
} else {
ans += ((d1 * d2) / 2) * (d * d);
}
}
if (yfull1 <= yfull2) {
ll uph = min(d - r.x1 % d, dim1);
ll color = 1 - (xr1 + yr1) % 2;
ll d2 = (yfull2 - yfull1 + 1);
if (d2 % 2 == 1) {
ans += ((d2 / 2) + (color == 0)) * uph * d;
} else {
ans += (d2 / 2) * uph * d;
}
if (xr1 != xr2) {
//ll downh = (r.x2 % d == 0 ? d : r.x2 % d);
ll downh = min(r.x2 % d + 1, dim1);
color = 1 - (xr2 + yr1) % 2;
if (d2 % 2 == 1) {
ans += ((d2 / 2) + (color == 0)) * downh * d;
} else {
ans += (d2 / 2) * downh * d;
}
}
}
if (xfull1 <= xfull2) {
ll lefth = min(d - r.y1 % d, dim2);
ll color = 1 - (xr1 + yr1) % 2;
ll d1 = (xfull2 - xfull1 + 1);
if (d1 % 2 == 1) {
ans += ((d1 / 2) + (color == 0)) * lefth * d;
} else {
ans += (d1 / 2) * lefth * d;
}
if (yr1 != yr2) {
//ll righth = (r.y2 % d == 0 ? d : r.y2 % d);
ll righth = min(r.y2 % d + 1, dim2);
color = 1 - (xr1 + yr2) % 2;
if (d1 % 2 == 1) {
ans += ((d1 / 2) + (color == 0)) * righth * d;
} else {
ans += (d1 / 2) * righth * d;
}
}
}
ll color = (xr1 + yr1) % 2;
ans += (color == 0) * min(d - r.x1 % d, dim1) * min(d - r.y1 % d, dim2);
if (yr1 != yr2) {
color = (xr1 + yr2) % 2;
//ans += (color == 0) * (d - r.x1 % d) * (r.y2 % d == 0 ? d : r.y2 % d);
ans += (color == 0) * min(d - r.x1 % d, dim1) * min(r.y2 % d + 1, dim2);
}
if (xr1 != xr2) {
color = (xr2 + yr1) % 2;
//ans += (color == 0) * (r.x2 % d == 0 ? d : r.x2 % d) * (d - r.y1 % d);
ans += (color == 0) * min(r.x2 % d + 1, dim1) * min(d - r.y1 % d, dim2);
}
if (xr1 != xr2 && yr1 != yr2) {
color = (xr2 + yr2) % 2;
//ans += (color == 0) * (r.x2 % d == 0 ? d : r.x2 % d) * (r.y2 % d == 0 ? d : r.y2 % d);
ans += (color == 0) * min(r.x2 % d + 1, dim1) * min(r.y2 % d + 1, dim2);
}
return ans;
}
ll calc(ll d, ll n, const vector<Rectangle>& rect) {
ll answhite = 0, ansblack = 0;
ll cnt = n / d;
ll needwhite = (cnt * cnt) / 2 * d * d, needblack = n * n - needwhite;
for (const auto& r : rect) {
ll cur = paint(d, n, r);
answhite += cur;
ansblack += r.area() - cur;
needwhite -= (r.area() - cur);
needblack -= cur;
}
answhite += needwhite;
ansblack += needblack;
return min(answhite, ansblack);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ll n;
int k;
cin >> n >> k;
vector<Rectangle> rect;
for (int i = 0; i < k; ++i) {
ll x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
rect.push_back(Rectangle(x1 - 1, y1 - 1, x2 - 1, y2 - 1));
}
ll ans = INF;
for (ll d = 1; d * d <= n; ++d) {
if (n % d == 0) {
ans = min(ans, calc(d, n, rect));
if (d != 1 && d * d != n) {
ans = min(ans, calc(n / d, n, rect));
}
}
}
cout << ans << '\n';
}
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/
/*
4 1
4 1 4 4
*/
