#include <bits/stdc++.h> using namespace std; #define ll long long const int INF=1e9+10; int main() { ll n, k; while(cin>>n>>k){ ll x[k], x2[k], y[k], y2[k]; for(int i=0; i<k; i++){ cin>>x[i]>>y[i]>>x2[i]>>y2[i]; } vector<ll> v; for(ll i=1; i<=sqrtl(n); i++){ if(n%i==0){ v.push_back(i); if(n!=i*i && i!=1){ v.push_back(n/i); } } } ll ans=LLONG_MAX, last_ans; for(auto& p : v){ last_ans=((((n/p)+1)>>1)*(((n/p)+1)>>1)+((n/p)>>1)*((n/p)>>1))*p*p; for(int i=0; i<k; i++){ ll k=(x[i])/p, d=(y[i])/p; if(k*p<x[i]){ k++; } if(d*p<y[i]){ d++; } if((k+d)%2==1){ last_ans++; }else{ last_ans--; } } ans=min(ans, min(last_ans, n*n-last_ans)); } cout<<ans<<'\n'; } }