#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxK = 1e5;
struct rectangle {
int l1, c1, l2, c2;
};
int l;
rectangle black[maxK];
int nxt( int x ) {
return (x / l + 1) * l;
}
int prv( int x ) {
return x / l * l - 1;
}
long long wbSq( int lin, int col, bool color ) {
if ( lin == 0 || col == 0 )
return 0;
return ((lin / 2) * ((col + 1) / 2) + ((lin + 1) / 2) * (col / 2) - ((lin + 1) / 2) * ((col + 1) / 2) - ((lin / 2) * (col / 2))) * (color == 0 ? 1 : -1);
}
long long getCost( rectangle r ) {
int l1 = r.l1, c1 = r.c1, l2 = r.l2, c2 = r.c2;
long long cost = 0;
if ( l1 / l == l2 / l && c1 / l == c2 / l )
cost += (l2 - l1 + 1) * (c2 - c1 + 1) * wbSq( 1, 1, (l1 / l + c1 / l) % 2 );
else if ( l1 / l == l2 / l ) {
cost += (l2 - l1 + 1) * (nxt( c1 ) - c1) * wbSq( 1, 1, (l1 / l + c1 / l) % 2 );
cost += (l2 - l1 + 1) * (c2 - prv( c2 )) * wbSq( 1, 1, (l2 / l + c2 / l) % 2 );
cost += l * (l2 - l1 + 1) * wbSq( 1, c2 / l - c1 / l - 1, (l1 / l + nxt( c1 ) / l) % 2 );
} else if ( c1 / l == c2 / l ) {
cost += (nxt( l1 ) - l1) * (c2 - c1 + 1) * wbSq( 1, 1, (l1 / l + c2 / l) % 2 );
cost += (l2 - prv( l2 )) * (c2 - c1 + 1) * wbSq( 1, 1, (l2 / l + c2 / l) % 2 );
cost += l * (c2 - c1 + 1) * wbSq( l2 / l - l1 / l - 1, 1, (nxt( l1 ) / l + c1 / l) % 2 );
} else {
cost += (nxt( l1 ) - l1) * (nxt( c1 ) - c1) * wbSq( 1, 1, (l1 / l + c1 / l) % 2 );
cost += (nxt( l1 ) - l1) * (c2 - prv( c2 )) * wbSq( 1, 1, (l1 / l + c2 / l) % 2 );
cost += (l2 - prv( l2 )) * (nxt( c1 ) - c1) * wbSq( 1, 1, (l2 / l + c1 / l) % 2 );
cost += (l2 - prv( l2 )) * (c2 - prv( c2 )) * wbSq( 1, 1, (l2 / l + c2 / l) % 2 );
cost += l * (nxt( l1 ) - l1) * wbSq( 1, c2 / l - c1 / l - 1, (l1 / l + nxt( c1 ) / l) % 2 );
cost += l * (nxt( c1 ) - c1) * wbSq( l2 / l - l1 / l - 1, 1, (nxt( l1 ) / l + c1 / l) % 2 );
cost += l * (l2 - prv( l2 )) * wbSq( 1, c2 / l - c1 / l - 1, (l2 / l + nxt( c1 ) / l) % 2 );
cost += l * (c2 - prv( c2 )) * wbSq( l2 / l - l1 / l - 1, 1, (nxt( l1 ) / l + c2 / l) % 2 );
cost += l * l * wbSq( l2 / l - l1 / l - 1, c2 / l - c1 / l - 1, (nxt( l1 ) / l + nxt( c1 ) / l) % 2 );
}
return cost;
}
signed main() {
int n, k;
long long cost, minCost;
cin >> n >> k;
for ( int i = 0; i < k; i++ ) {
cin >> black[i].l1 >> black[i].c1 >> black[i].l2 >> black[i].c2;
black[i].l1--;
black[i].c1--;
black[i].l2--;
black[i].c2--;
}
minCost = n * n;
for ( l = 1; l < n; l++ ) {
if ( n % l == 0 ) {
int x = (n / l + 1) / 2, y = n / l / 2;
cost = (l * l) * (x * x + y * y);
for ( int i = 0; i < k; i++ )
cost += getCost( black[i] );
minCost = min( minCost, cost );
cost = 2 * x * y * l * l;
for ( int i = 0; i < k; i++ )
cost -= getCost( black[i] );
minCost = min( minCost, cost );
}
}
cout << minCost;
return 0;
}
