/*
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
\\ //
// 271828___182845__904523__53602__ \\
\\ 87___47____13______52____66__24_ //
// 97___75____72______47____09___36 \\
\\ 999595_____74______96____69___67 //
// 62___77____24______07____66__30_ \\
\\ 35___35____47______59____45713__ //
// \\
\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>
using namespace std;
using ll = long long;
const int N = 3e5 + 5;
const ll mod = 1e9 + 7, inf = 1e18;
struct rec {
ll x1, y1, x2, y2;
};
bool ev_od(ll x, ll y, ll side) {
ll xx = (x + side - 1) / side, yy = (y + side - 1) / side;
if (xx % 2 == yy % 2) return 0;
return 1;
}
void solve() {
ll n, k; cin >> n >> k;
vector<rec> v(k);
for (int i = 0; i < k; ++i) {
cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2;
}
ll ans = n * n;
for (int i = 1; i < n; ++i) {
if (n % i) continue;
ll od = 0, ev = 0;
for (rec& j : v) {
// (j.x2 - j.x1 + 1) X (j.y2 - j.y1 + 1)
ll len_x = j.x2 - j.x1 + 1, len_y = j.y2 - j.y1 + 1;
ll toshni_x = len_x / i * i, toshni_y = len_y / i * i;
if (ev_od(j.x1, j.y1, i)) {
//cout << "TAMAMA?\n";
ll obshi = toshni_x / i * toshni_y / i;
od += (obshi + 1) / 2 * i * i;
ev += obshi / 2 * i * i;
//cout << obshi << "\n";
}
else {
//cout << "TAMAMA?\n";
ll obshi = toshni_x / i * toshni_y / i;
od += obshi / 2 * i * i;
ev += (obshi + 1) / 2 * i * i;
//cout << obshi << "\n";
}
//cout << od << " " << ev << "\n";
//break;
ll new_x = j.x1 + toshni_x - 1, new_y = j.y1 + toshni_y - 1;
//cout << new_x << " " << new_y << "\n";
ll w = j.x2 - new_x, h = new_y - j.y1;
ll c = h / i;
if (ev_od(new_x + 1, j.y1, i)) {
od += (c + 1) / 2 * w * i;
ev += c / 2 * w * i;
}
else {
od += c / 2 * w * i;
ev += (c + 1) / 2 * w * i;
}
h = j.y2 - new_y, w = new_x - j.x1;
c = w / i;
if (ev_od(j.x1, new_y + 1, i)) {
od += (c + 1) / 2 * h * i;
ev += c / 2 * h * i;
}
else {
od += c / 2 * h * i;
ev += (c + 1) / 2 * h * i;
}
if (ev_od(new_x + 1, new_y + 1, i)) {
od += (j.x2 - new_x) * (j.y2 - new_y);
}
else {
ev += (j.x2 - new_x) * (j.y2 - new_y);
}
//cout << od << " " << ev << "\n";
}
/*ll edge = n / i, c = (edge * edge + 1) / 2;
ll a = od + c * i * i - ev;
c = edge * edge / 2;
ll b = ev + c * i * i - od;
cout << a << " " << b << " ";
ans = min({ ans, a, b });*/
//swap(ev, od);
//cout << od << " " << ev << "\n";
ll edge = n / i;
ll yndhanur_zuyg = (edge * edge + 1) / 2 * i * i, yndhanur_kent = (edge * edge) / 2 * i * i;
//cout << od << " " << ev << "\n";
//cout << yndhanur_kent << " " << yndhanur_zuyg << "\n";
ll bl = yndhanur_zuyg - ev + od;
ans = min(ans, bl);
ll wh = yndhanur_kent - od + ev;
ans = min(ans, wh);
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
//int t; cin >> t;
//while (t--)
solve();
}
