#include <iostream>
using namespace std;
long long n, x, x2;
int k, t;
void f()
{
x = n*n/2;
for(int i = n/2; i >= 1; --i)
if(n % i == 0)
x = min(x, i*i*((n/i)*(n/i)/2));
cout << x;
}
bool isprime(long long x)
{
if(x < 2) return 0;
if(x == 2 || x == 3) return 1;
if(x % 2 == 0 || x % 3 == 0) return 0;
for(int i = 5; i * i <= n; i += 6)
if(x % i == 0 || x % (i+2) == 0)
return 0;
return 1;
}
void f2()
{
x = n*n/2;
x2 = x + 1;
for(int c = 0, i1, i2, j1, j2; c < k; ++c)
{
cin >> i1 >> j1 >> i2 >> j2;
for(int i = i1; i <= i2; ++i)
for(int j = j1; j <= j2; ++j)
{
if(i % 2 == j % 2) x++, x2--;
if(i % 2 != j % 2) x2++, x--;
}
}
cout << min(x, x2);
}
int main()
{
cin >> n >> k;
if(k == 0) f();
else if(isprime(n)) f2();
return 0;
}
