#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
const int MAXN = (int) 1e5;
struct Data {
int x1, y1, x2, y2;
}arr[MAXN + 1];
inline void add(vector <ll> &fr, ll a, ll b) {
fr[0] += a;
fr[1] += b;
}
inline int get(int x, int len) {
if(x - len + 1 < 0) {
return -1;
}
return ((x - len + 1) / len) * len + len - 1;
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n, k;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for(i = 1; i <= k; i++) {
cin >> arr[i].x1 >> arr[i].y1 >> arr[i].x2 >> arr[i].y2;
arr[i].x1--, arr[i].y1--;
arr[i].x2--, arr[i].y2--;
}
ll ans = 1LL * n * n;
for(int len = 1; len < n; len++) {
if(n % len == 0) {
vector <ll> fr(2);
for(i = 1; i <= k; i++) {
if(arr[i].x2 / len == arr[i].x1 / len && arr[i].y2 / len == arr[i].y1 / len) {
if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
fr[0] += 1LL * (arr[i].x2 - arr[i].x1 + 1) * (arr[i].y2 - arr[i].y1 + 1);
}
else {
fr[1] += 1LL * (arr[i].x2 - arr[i].x1 + 1) * (arr[i].y2 - arr[i].y1 + 1);
}
continue;
}
int a = ((arr[i].x1 + len - 1) / len) * len - arr[i].x1;
int A = ((arr[i].y1 + len - 1) / len) * len - arr[i].y1;
int b = arr[i].x2 - get(arr[i].x2, len);
int B = arr[i].y2 - get(arr[i].y2, len);
if(arr[i].y2 / len == arr[i].y1 / len) {
if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
add(fr, 1LL * a * (arr[i].y2 - arr[i].y1 + 1), 0);
}
else {
add(fr, 0, 1LL * a * (arr[i].y2 - arr[i].y1 + 1));
}
if(((arr[i].x1 + a) / len + arr[i].y1 / len) % 2 == 0) {
int cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
add(fr, 1LL * len * ((cur + 1) / 2) * (arr[i].y2 - arr[i].y1 + 1), 1LL * len * (cur / 2) * (arr[i].y2 - arr[i].y1 + 1));
}
else {
int cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
add(fr, 1LL * len * (cur / 2) * (arr[i].y2 - arr[i].y1 + 1), 1LL * len * ((cur + 1) / 2) * (arr[i].y2 - arr[i].y1 + 1));
}
if((arr[i].x2 / len + arr[i].y1 / len) % 2 == 0) {
add(fr, 1LL * b * (arr[i].y2 - arr[i].y1 + 1), 0);
}
else {
add(fr, 0, 1LL * b * (arr[i].y2 - arr[i].y1 + 1));
}
continue;
}
if(arr[i].x2 / len == arr[i].x1 / len) {
if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
add(fr, 1LL * A * (arr[i].x2 - arr[i].x1 + 1), 0);
}
else {
add(fr, 0, 1LL * A * (arr[i].x2 - arr[i].x1 + 1));
}
if(((arr[i].y1 + A) / len + arr[i].x1 / len) % 2 == 0) {
int cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
add(fr, 1LL * len * ((cur + 1) / 2) * (arr[i].x2 - arr[i].x1 + 1), 1LL * len * (cur / 2) * (arr[i].x2 - arr[i].x1 + 1));
}
else {
int cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
add(fr, 1LL * len * (cur / 2) * (arr[i].x2 - arr[i].x1 + 1), 1LL * len * ((cur + 1) / 2) * (arr[i].x2 - arr[i].x1 + 1));
}
if((arr[i].x1 / len + arr[i].y2 / len) % 2 == 0) {
add(fr, 1LL * B * (arr[i].x2 - arr[i].x1 + 1), 0);
}
else {
add(fr, 0, 1LL * B * (arr[i].x2 - arr[i].x1 + 1));
}
continue;
}
/*if(len == 2) {
cerr << a << " " << A << " " << b << " " << B << "\n";
}*/
if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
add(fr, 1LL * a * A, 0);
}
else {
add(fr, 0, 1LL * a * A);
}
int cur;
if((arr[i].x1 / len + (arr[i].y1 + A) / len) % 2 == 1) {
cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
add(fr, 1LL * len * (cur / 2) * a, 1LL * len * ((cur + 1) / 2) * a);
}
else {
cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
add(fr, 1LL * len * ((cur + 1) / 2) * a, 1LL * len * (cur / 2) * a);
}
if(((arr[i].x1 + a) / len + arr[i].y1 / len) % 2 == 1) {
cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
add(fr, 1LL * len * (cur / 2) * A, 1LL * len * ((cur + 1) / 2) * A);
}
else {
cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
add(fr, 1LL * len * ((cur + 1) / 2) * A, 1LL * len * (cur / 2) * A);
}
//////////////////////////////////
if((arr[i].x1 / len + arr[i].y2 / len) % 2 == 0) {
add(fr, 1LL * a * B, 0);
}
else {
add(fr, 0, 1LL * a * B);
}
if((arr[i].x2 / len + arr[i].y1 / len) % 2 == 0) {
add(fr, 1LL * b * A, 0);
}
else {
add(fr, 0, 1LL * b * A);
}
//////////////////////////////////////
if((arr[i].x2 / len + arr[i].y2 / len) % 2 == 0) {
add(fr, 1LL * b * B, 0);
}
else {
add(fr, 0, 1LL * b * B);
}
if(((arr[i].x2 - b) / len + arr[i].y2 / len) % 2 == 1) {
cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
add(fr, 1LL * len * (cur / 2) * B, 1LL * len * ((cur + 1) / 2) * B);
}
else {
cur = (arr[i].x2 - arr[i].x1 + 1 - a - b) / len;
add(fr, 1LL * len * ((cur + 1) / 2) * B, 1LL * len * (cur / 2) * B);
}
if((arr[i].x2 / len + (arr[i].y2 - B) / len) % 2 == 1) {
cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
add(fr, 1LL * len * (cur / 2) * b, 1LL * len * ((cur + 1) / 2) * b);
}
else {
cur = (arr[i].y2 - arr[i].y1 + 1 - A - B) / len;
add(fr, 1LL * len * ((cur + 1) / 2) * b, 1LL * len * (cur / 2) * b);
}
///////////////////////////////
ll cnt0, cnt1;
ll s = 1LL * (arr[i].x2 - arr[i].x1 + 1 - a - b) * (arr[i].y2 - arr[i].y1 + 1 - A - B);
if((s / (1LL * len * len)) % 2 == 0) {
cnt0 = cnt1 = (s / (1LL * len * len)) / 2;
}
else {
cnt0 = cnt1 = (s / (1LL * len * len)) / 2;
if((arr[i].x1 / len + arr[i].y1 / len) % 2 == 0) {
cnt0++;
}
else {
cnt1++;
}
}
fr[0] += 1LL * len * len * cnt0;
fr[1] += 1LL * len * len * cnt1;
}
ll cnt0, cnt1;
if((n / len) % 2 == 0) {
cnt0 = cnt1 = ((1LL * n * n) / (1LL * len * len)) / 2;
}
else {
cnt0 = cnt1 = ((1LL * n * n) / (1LL * len * len)) / 2;
cnt0++;
}
cnt0 *= 1LL * len * len;
cnt1 *= 1LL * len * len;
//cerr << len << " " << cnt0 << " " << cnt1 << " " << fr[0] << " " << fr[1] << "\n";
ans = min(ans, min(cnt0 - fr[0] + fr[1], cnt1 - fr[1] + fr[0]));
}
}
cout << ans;
//cin.close();
//cout.close();
return 0;
}
