#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 12;
#define int long long
unordered_map<int,int> odd[N],even[N];
ll col_eq(int k,int x,int y,int x1,int y1){
int ret = 0;
for(int i = x;i <= x1;i++){
for(int j = y;j <= y1;j++){
if(((i + k - 1) / k) % 2 == ((j + k - 1) / k) % 2){
ret++;
}
}
}
// ll ret = (odd[x1][k] - odd[x - 1][k]) * (odd[y1][k] - odd[y - 1][k]);
// ret += (even[x1][k] - even[x - 1][k]) *1ll* (even[y1][k] - even[y - 1][k]);
return ret;
}
ll col_non_eq(int k,int x,int y,int x1,int y1){
return (x1 - x + 1) *1ll* (y1 - y + 1) - col_eq(k,x,y,x1,y1);
}
vector<pair<pair<int,int>,pair<int,int>>> a;
ll n,k;
int get(ll del){
ll res1 = 0,res2 = 0;
for(auto [x,y]:a){
res1 += col_eq(del,x.first,x.second,y.first,y.second);
res2 += col_non_eq(del,x.first,x.second,y.first,y.second);
}
ll x = res1;
res1 = ((n * n / del / del) + 1) / 2 * (del * del) - res1 + res2;
res2 = ((n * n / del / del)) / 2 * (del * del) + x - res2;
// cout << ((n * n / del / del) + 1) / 2 * del * del - res2 << '\n';
return min(res1,res2);
}
void test(){
cin >> n >> k;
for(int i = 1;i <= k;i++){
int x,y,x1,y1;
cin >> x >> y >> x1 >> y1;
a.push_back({{x,y},{x1,y1}});
}
ll res = 1e10;
for(int i = 1;i < n;i++){
if(n % i == 0){
// for(int j = 1;j <= n;j++){
// int x = (j + i - 1) / i;
// odd[j][i] = odd[j - 1][i];
// even[j][i] = even[j - 1][i];
// if(x & 1){
// odd[j][i]++;
// }else{
// even[j][i]++;
// }
// }
}
}
for(int i = 1;i < n;i++){
if(n % i == 0){
res = min(res,1ll*get(i));
}
}
cout << res;
}
main(){
ios_base::sync_with_stdio(0);cin.tie(0);
test();
}
