import sys
input = sys.stdin.readline
n,k = map(int,input().split())
# l = [0]*n
start = [0]*n
end = [0]*n
for _ in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    start[a] += 1
    end[b] += 1
 
balance = 0
ans = []
for i in range(n):
    e1 = start[i]
    e2 = end[i]
    total = 0
    if e1 >= e2:
        total += e1
        total += balance
        balance += (e1-e2)
 
    else:
        total += e1
        total += balance
        balance -= (e2-e1)
 
    ans.append(total)
 
ans.sort()
# if n%2 == 1:
sys.stdout.write(str(ans[n//2])+"\n")

aW1wb3J0IHN5cwppbnB1dCA9IHN5cy5zdGRpbi5yZWFkbGluZQpuLGsgPSBtYXAoaW50LGlucHV0KCkuc3BsaXQoKSkKIyBsID0gWzBdKm4Kc3RhcnQgPSBbMF0qbgplbmQgPSBbMF0qbgpmb3IgXyBpbiByYW5nZShrKToKICAgIGEsYiA9IG1hcChpbnQsaW5wdXQoKS5zcGxpdCgpKQogICAgYSAtPSAxCiAgICBiIC09IDEKICAgIHN0YXJ0W2FdICs9IDEKICAgIGVuZFtiXSArPSAxCiAKYmFsYW5jZSA9IDAKYW5zID0gW10KZm9yIGkgaW4gcmFuZ2Uobik6CiAgICBlMSA9IHN0YXJ0W2ldCiAgICBlMiA9IGVuZFtpXQogICAgdG90YWwgPSAwCiAgICBpZiBlMSA+PSBlMjoKICAgICAgICB0b3RhbCArPSBlMQogICAgICAgIHRvdGFsICs9IGJhbGFuY2UKICAgICAgICBiYWxhbmNlICs9IChlMS1lMikKIAogICAgZWxzZToKICAgICAgICB0b3RhbCArPSBlMQogICAgICAgIHRvdGFsICs9IGJhbGFuY2UKICAgICAgICBiYWxhbmNlIC09IChlMi1lMSkKIAogICAgYW5zLmFwcGVuZCh0b3RhbCkKIAphbnMuc29ydCgpCiMgaWYgbiUyID09IDE6CnN5cy5zdGRvdXQud3JpdGUoc3RyKGFuc1tuLy8yXSkrIlxuIik=