//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mpr make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax = 100011, mod = 1000000007, inf = 2000010000, key = 200003, lg = 20, block = 300;
const ll infll = 4000000000000000000;
const ld eps = 1e-9;
ll calc1(ll x, ll y, ll side) {
if(x <= 0 || y <= 0)
return 0;
ll wholex = x / side;
ll wholey = y / side;
ll ans = (wholex * wholey + 1) / 2 * side * side;
ll width = x - wholex * side;
ll length = y;
ll t = length / (2 * side) * side + min(side, length % (2 * side));
if(wholex % 2 == 1)
t = length - t;
ans += t * width;
if(ans != t * width) {
width = y - wholey * side;
length = wholex * side;
t = length / (2 * side) * side + min(side, length % (2 * side));
if(wholey % 2 == 1)
t = length - t;
ans += t * width;
}
//cout << x << " " << y << " " << side << " " << ans << " x y side ans\n";
return ans;
}
ll calc(ll x1, ll y1, ll x2, ll y2, ll side) {
ll ans = calc1(x2, y2, side) - calc1(x2, y1 - 1, side) - calc1(x1 - 1, y2, side) + calc1(x1 - 1, y1 - 1, side);
//cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << side << " " << ans << " rect side ans\n";
return ans;
}
void solve()
{
ll n, k;
cin >> n >> k;
vector<array<ll, 4>> rect(k);
ll blackeven, totaleven, totalblack = 0, ans = n * n;
for(int i = 0; i < k; i++) {
cin >> rect[i][0] >> rect[i][1] >> rect[i][2] >> rect[i][3];
totalblack += (rect[i][2] - rect[i][0] + 1) * (rect[i][3] - rect[i][1] + 1);
}
//cout << totalblack << " totalblack\n";
for(ll j = 1; j < n; j++) {
if(n % j != 0)
continue;
blackeven = 0;
for(int i = 0; i < k; i++)
blackeven += calc(rect[i][0], rect[i][1], rect[i][2], rect[i][3], j);
//cout << blackeven << " blackeven\n";
totaleven = n * n;
if((n / j) % 2 == 1)
totaleven += j * j;
totaleven /= 2;
//cout << totaleven << " totaleven\n";
ans = min(ans, totaleven - 2 * blackeven + totalblack);
ans = min(ans, n * n - totaleven + 2 * blackeven - totalblack);
}
cout << ans << "\n";
return ;
}
int main()
{
//freopen("wormsort.in","r",stdin);
//freopen("wormsort.out","w",stdout);
ios_base::sync_with_stdio(0);cin.tie(0);
srand(8713);
//init();
int t = 1;
//cin >> t;
//int t_ = t;
//t = rdi();
while(t--) {
//cout << "Case #" << t_ - t << ": ";
solve();
}
//flush();
return 0;
}
/*
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
*/
