/** @BY_KUTBILIM **/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).end()
const int inf = (int)1e9+7;
int main(){
ios_base::sync_with_stdio(false);
cin.tie();
int k;
ll n;
cin >> n >> k;
int x1[k], x2[k], y1[k], y2[k];
vector<ll> div;
div.pb(1);
for(int i = 2; i <= sqrt(n); i++){
if(n % i == 0){
div.pb(i);
if(i != n / i){
div.pb(n/i);
}
}
}
sort(all(div));
vector<ll> cnt1((int)div.size(), 0), cnt0((int)div.size(), 0);
for(int i = 0; i < k; i++){
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
x1[i]--;
y1[i]--;
for(int j = 0; j < (int)div.size(); j++){
if((x1[i] / div[j] + y1[i] / div[j]) % 2 == 0)cnt0[j]++;
else cnt1[j]++;
}
}
ll ans = n * n;
for(int i = 0; i < (int)div.size(); i++){
ans = min({ans,
n * n / (div[i] * div[i]) / 2ll * (div[i] * div[i]) + (div[i] * div[i]) - cnt0[i] + cnt1[i],
n * n / (div[i] * div[i]) / 2ll * (div[i] * div[i]) - cnt1[i] + cnt0[i]});
}
cout << ans;
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
*/
