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")