#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N], n, m, k;
void solve(int test_case){
int i, j;
cin >> n >> k;
vector<pii> v;
for(i=0;i<k;i++){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
v.pb({x1, y1});
}
int ans = mod;
for(int s=1; (int)s*s<=n; s++){
if(n%s == 0){
{
int tmp = (int)s*s;
int sum = ((int)((int)n*n/tmp)/2ll)*tmp;
int sz = (s);
int ans1=sum;
for(i=0;i<k;i++){
auto [x, y] = v[i];
x+=sz-1, y+=sz-1;
x/=sz, y/=sz;
if((x+y)%2 == 0){
ans1++;
}else ans1--;
}
ans = min(ans, ans1);
// cout << ans << ' ';
if(((int)n*n/tmp)%2!=0)sum += tmp;
ans1 = sum;
for(i=0;i<k;i++){
auto [x, y] = v[i];
x+=sz-1, y+=sz-1;
x/=sz, y/=sz;
if((x+y)%2 == 1){
ans1++;
}else ans1--;
}
ans = min(ans, ans1);
// cout << ans << ' ';
}
if((int)s*s != n && s != 1){
int sz = ((int)n/s);
int tmp = (int)(sz)*(sz);
int sum = ((int)((int)n*n/tmp)/2ll)*tmp;
int ans1=sum;
for(i=0;i<k;i++){
auto [x, y] = v[i];
x+=sz-1, y+=sz-1;
x/=sz, y/=sz;
if((x+y)%2 == 0){
ans1++;
}else ans1--;
}
ans = min(ans, ans1);
// cout << ans << ' ';
if((int)((int)n*n/tmp)%2ll!=0)sum += tmp;
ans1 = sum;
for(i=0;i<k;i++){
auto [x, y] = v[i];
x+=sz-1, y+=sz-1;
x/=sz, y/=sz;
if((x+y)%2 == 1){
ans1++;
}else ans1--;
}
ans = min(ans, ans1);
// cout << ans << ' ';
}
}
}
cout << ans << '\n';
return;
}
/*
4 4
4 1 4 1
4 2 4 2
4 3 4 3
4 4 4 4
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
5 4
1 2 1 2
1 3 1 3
1 4 1 4
2 2 2 2
3 9
1 1 1 1
2 2 2 2
3 3 3 3
1 2 1 2
1 3 1 3
2 1 2 1
3 1 3 1
3 2 3 2
2 3 2 3
*/
signed main(){
FASTIO;
#define MULTITEST 0
#if MULTITEST
int ___T;
cin >> ___T;
for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
