#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 tr[N * 4][2], lazy[N * 4];

void update(int i) {
    tr[i][0] = tr[i * 2][0] * (lazy[i * 2] <= 0) + tr[i * 2 + 1][0] * (lazy[i * 2 + 1] <= 0);
    tr[i][1] = tr[i * 2][1] * (lazy[i * 2] <= 0) + tr[i * 2 + 1][1] * (lazy[i * 2 + 1] <= 0);
}

void build(int i, int l, int r, int m) {
    lazy[i] = 0;
    if(l + 1 == r) {
        tr[i][0] = tr[i][1] = 0;
        tr[i][l / m % 2] = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(i * 2, l, mid, m);
    build(i*2+1, mid, r, m);
    tr[i][0] = tr[i * 2][0] + tr[i * 2 + 1][0];
    tr[i][1] = tr[i * 2][1] + tr[i * 2 + 1][1];
}

void modify(int i, int l, int r, int ql, int qr, int x) {
    if(l >= qr || r <= ql) return;
    if(l >= ql && r <= qr) {
        lazy[i] += x;
        return;
    }
    int mid = (l + r) / 2;
    modify(i * 2, l, mid, ql, qr, x);
    modify(i*2+1, mid, r, ql, qr, x);
    update(i);
}

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;

        for(int j = 0; j < n; j ++) {
            for(auto &[l, r] : sl[j])
                modify(1, 0, n, l, r, 1);
            
            for(auto &[l, r] : sr[j])
                modify(1, 0, n, l, r, -1);
            
            if(j % i == 0) swap(a, b);
            int x = tr[1][0] * (lazy[1] <= 0), y = tr[1][1] * (lazy[1] <= 0);
            a += x + s1 - y;
            b += y + s0 - x;
        }

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