#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k, cnt, x, y, xx, yy;
ll a[3][3];
void subt1()
{
ll mn = INT_MAX;
for ( int i = 1; i < n; i ++ ){
if ( n % i == 0 ) {
ll c = 0;
for ( int j = 1; j <= (n/i); j ++ ) {
if ( j % 2 ) {
c += (i*i) * ( ( n/i ) / 2 );
}
else {
c += (i*i) * ( ( ( n/i ) + 1 ) / 2 );
}
}
mn = min( mn, c );
}
}
cout << mn;
exit(0);
}
void subt2()
{
ll c1, c2;
c1 = c2 = 0;
for ( int i = 1; i <= k; i ++ ) {
cin >> x >> y >> xx >> yy;
a[x%2][y%2] ++;
}
c1 = (n*n)/2;
c2 = c1 + 1;
c1 = c1 - ( a[1][0] + a[0][1] );
c1 = c1 + ( a[1][1] + a[0][0] );
c2 = c2 - ( a[1][1] + a[0][0] );
c2 = c2 + ( a[1][0] + a[0][1] );
cout << min( c1, c2 );
exit(0);
}
int main()
{
cin >> n >> k;
for ( int i = 1; i <= n; i ++ ) {
if ( n % i == 0 ) cnt ++;
}
if ( cnt == 2 ) subt2();
subt1();
}
