#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using pii = pair<int, int>;

const int N = 1e5 + 10;

vector<pii> sl[N], sr[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    for(int i = 0, x1, y1, x2, y2; i < k; i ++) {
        cin >> x1 >> y1 >> x2 >> y2;
        x1 --;
        y1 --;
        sl[x1].emplace_back(y1, y2);
        sr[x2].emplace_back(y1, y2);
    }
    
    i64 ans = n * (i64)n;
    for(int i = 1; i < n; i ++) {
        if(n % i) continue;
        build(1, 0, n, i);

        i64 a = 0, b = 0;
        int s0 = (n / i + 1) / 2 * i, s1 = n - s0, ta = 0, tb = 0;

        for(int j = 0; j < n; j ++) {
            for(auto &[l, r] : sl[j]) {
                int x = calc(i, r) - calc(i, l);
                ta += x;
                tb += r - l - x;
            }
            
            for(auto &[l, r] : sr[j]) {
                int x = calc(i, r) - calc(i, l);
                ta -= x;
                tb -= r - l - x;
            }
            
            if(j % i == 0) swap(a, b);
            a += ta + s1 - tb;
            b += tb + s0 - ta;
        }

        if(a < ans) ans = a;
        if(b < ans) ans = b;
    }
    cout << ans << "\n";
}

/*
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
*/

answer.code: In function ‘int main()’:
answer.code:29:9: error: ‘build’ was not declared in this scope
   29 |         build(1, 0, n, i);
      |         ^~~~~
answer.code:36:25: error: ‘calc’ was not declared in this scope
   36 |                 int x = calc(i, r) - calc(i, l);
      |                         ^~~~
answer.code:42:25: error: ‘calc’ was not declared in this scope
   42 |                 int x = calc(i, r) - calc(i, l);
      |                         ^~~~