/*
Sviatoslav Bidzilia 2019
CF: anakib1
*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <chrono>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <deque>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdarg.h>
#include <utility>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unisgned long long
#define ld long double
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define pii pair<int, int>
#define tii triple<int, int, int>
#define e 1e-7
#define PI acos(-1)
#define inf 1e17
#define vi vector<int>
#define F first
#define S second
#define rng(x) for(int _ = 0; _ < (x); _++)
#define rngi(i, x) for(int i = 0; i < (x); i++)
#define rngsi(s, i, x) for(int i = (s); i <(x); i++)
#define int long long
template<typename A, typename B, typename C>
struct triple
{
A X;
B Y;
C Z;
triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
};
template<typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0)
{
return triple<A, B, C>(a, b, c);
}
template<typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b)
{
if (a.X != b.X)
return a.X < b.X;
if (a.Y != b.Y)
return a.Y < b.Y;
return a.Z < b.Z;
}
template<typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p)
{
ofs << "( " << p.F << " , " << p.S << " )";
return ofs;
}
template<typename T>
void print(T a)
{
for (auto i : a)
cout << i << ' ';
cout << '\n';
}
template<typename T>
T max(T a, T b, T c)
{
return max(a, max(b, c));
}
template<typename T>
T min(T a, T b, T c)
{
return min(a, min(b, c));
}
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int sz, flx, fly, d, s, d1, d2;
int n;
vector<pair<pii, pii> > rect;
inline int sum1(int x, int y, int k)
{
y--, x--;
sz = k * k;
flx = (x + 1) / k;
fly = (y + 1) / k;
int ans = fly / 2 * sz * flx;
if (fly & 1)
{
ans += flx / 2 * sz;
if (flx & 1)
ans += sz;
}
if ((x + 1) % k)
{
d = (x + 1) % k;
s = (flx + 1) & 1;
ans += fly / 2 * k * d;
if (fly & 1 && s)
ans += k * d;
}
if ((y + 1) % k != 0)
{
d = (y + 1) % k;
s = (fly + 1) & 1;
ans += flx / 2 * k * d;
if (flx & 1 && s)
ans += k * d;
}
if ((x + 1) % k && (y + 1) % k)
{
d1 = (x + 1) % k;
d2 = (y + 1) % k;
s = (fly + flx) & 1;
s ^= 1;
if (s)
ans += d1 * d2;
}
return ans;
}
inline int sum(int x, int y, int t, int k)
{
if (t)
return sum1(x, y, k);
else
return x * y - sum1(x, y, k);
}
inline int sumr(int x1, int y1, int x2, int y2, int t, int k)
{
if (x1 == x2 && y1 == y2)
{
int x = x1 / k - 1;
int y = y1 / k - 1;
if (x1 % k)
x++;
if (y1 % k)
y++;
if (!t)
return (x + y) & 1;
else
return (x + y + 1) & 1;
}
return sum(x2, y2, t, k) - (x1 > 1 ? sum(x1 - 1, y2, t, k) : 0) - (y1 > 1 ? sum(x2, y1 - 1, t, k) : 0) + (x1 > 1 && y1 > 1 ? sum(x1 - 1, y1 - 1, t, k) : 0);
}
inline int solve(int k, int t)
{
int ans = 0;
int cntb = 0;
int cntw = 0;
for (auto &i : rect)
{
int r = sumr(i.first.first, i.first.second, i.second.first, i.second.second, t, k);
cntb += r;
cntw += (i.second.second - i.first.second + 1) * (i.second.first - i.first.first + 1) - r;
}
int allb = sumr(1, 1, n, n, t, k);
cntw += allb - cntb;
return cntw;
}
signed main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
srand(time(NULL));
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
/*rng(20)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << sumr(a, b, c, d, 0, 3) << '\n';
}*/
int k;
scanf("%d%d", &n, &k);
rect.resize(k);
for (auto& i : rect)
scanf("%d%d%d%d", &i.first.second, &i.first.first, &i.second.second, &i.second.first);
vi divs;
for (int d = 2; d * d <= n; d++)
if (n % d == 0)
{
divs.pb(d);
divs.pb(n / d);
}
divs.pb(1);
SORT(divs);
divs.erase(unique(all(divs)), divs.end());
int ans = inf;
for (int m : divs)
ans = min(ans, solve(m, 0), solve(m, 1));
if (!rect.size())
for (auto m : divs)
ans = min(ans, sumr(1, 1, n, n, 1, m), sumr(1, 1, n, n, 0, m));
cout << ans << '\n';
}
