#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 2e5+5;
const int INF = 1e17;
int m_ceil(int a, int b)
{
if(a%b)
return ((a/b)+1);
else
return a/b;
}
int m_floor(int a, int b)
{
return a/b;
}
int intersect(int a, int b, int c, int d)
{
int L = max(a, c);
int R = min(b, d);
if(L > R)
return 0;
return R-L+1;
}
in solve1(int a, int b, int n)//{even, odd}
{
//compute even - odd difference for reference.
int L = b-a+1;
int G = (b-a)/(2*n); G*=(2*n);
b-=G;
if(b >= (a+2*n))
b-=(2*n);
//[a, b]
a%=(2*n);
b%=(2*n);
if(b < a)
b+=(2*n);
int g = intersect(a, b, 0, n-1) - intersect(a, b, n, 2*n-1) + intersect(a, b, 2*n, 3*n-1) - intersect(a, b, 3*n, 4*n-1);
return {(g+L)/2, (L-g)/2};
}
in solve3(int ax, int bx, int ay, int by, int n)
{
in a = {0,0};
for(int i = ax; i <= bx; i++)
{
for(int j = ay; j <= by; j++)
{
int G = (i/n);
int H = (j/n);
G+=H;
if(G%2 == 0)
a[0]++;
else
a[1]++;
}
}
return a;
}
in solve2(int ax, int bx, int ay, int by, int n)//see coloring as floor(i/k) + floor(j/k) mod 2.
{
auto x = solve1(ax, bx, n);
auto y = solve1(ay, by, n);
in z = {x[0]*y[0]+x[1]*y[1], x[0]*y[1]+x[1]*y[0]};
return z;
}
int comp(const vector<array<int, 4>> &rect, int N)
{
int ok = 0;
for(auto [ax, bx, ay, by]: rect)
{
auto [X, Y] = solve2(ax, bx, ay, by, N);
ok+=(X-Y);
}
return ok;
}
int win(const vector<array<int, 4>> &rect, int N, int n)
{
int diff = comp(rect, N);
//odd stuff is black. how many black?
int g = n/N; g*=g; g/=2; g*=N; g*=N;
return min(g + diff, n*n - g - diff);
}
signed main()
{
fast();
int n, k; cin >> n >> k;
vector<array<int, 4>> rect;
while(k--)
{
int ax, bx, ay, by; cin >> ax >> ay >> bx >> by;
ax--; bx--; ay--; by--;
rect.pb({ax, bx, ay, by});
}
int ans = INF;
for(int i = 1; i*i <= n; i++)
{
if(n%i)
continue;
if(i == n)
continue;
ans = min(ans, win(rect, i, n));
if(i != 1)
ans = min(ans, win(rect, n/i, n));
}
cout << ans << "\n";
return 0;
}
