#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e6 + 2;
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
 
    ll n, k;
    cin >> n >> k;
    vector<ll> diff(n + 2, 0);
 
    while(k--)
    {
        ll a, b;
        cin >> a >> b;
        diff[a]++;
        diff[b + 1]--;
    }
 
    for(ll i = 1 ; i <= n ; i++){
        diff[i] += diff[i - 1];
    }
    diff.pop_back();
    sort(diff.begin(), diff.end());
    cout << diff[(n + 2) / 2] << endl;
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsID0gbG9uZyBsb25nOwpjb25zdCBsbCBtYXhuID0gMWU2ICsgMjsKaW50IG1haW4oKSB7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgCiAgICBjaW4udGllKG51bGxwdHIpOwoKICAgIGxsIG4sIGs7CiAgICBjaW4gPj4gbiA+PiBrOwogICAgdmVjdG9yPGxsPiBkaWZmKG4gKyAyLCAwKTsKICAgICAKICAgIHdoaWxlKGstLSkKICAgIHsKICAgICAgICBsbCBhLCBiOwogICAgICAgIGNpbiA+PiBhID4+IGI7CiAgICAgICAgZGlmZlthXSsrOwogICAgICAgIGRpZmZbYiArIDFdLS07CiAgICB9CgogICAgZm9yKGxsIGkgPSAxIDsgaSA8PSBuIDsgaSsrKXsKICAgICAgICBkaWZmW2ldICs9IGRpZmZbaSAtIDFdOwogICAgfQogICAgZGlmZi5wb3BfYmFjaygpOwogICAgc29ydChkaWZmLmJlZ2luKCksIGRpZmYuZW5kKCkpOwogICAgY291dCA8PCBkaWZmWyhuICsgMikgLyAyXSA8PCBlbmRsOwoKICAgIHJldHVybiAwOwp9Cg==

NyA0CjUgNQoyIDQKNCA2CjMgNQ==

7 4
5 5
2 4
4 6
3 5