#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int n, k;
	cin >> n >> k;
	vector<int> diff(n + 1);
	// leer la entrada y construir el arreglo de diferencias
	for (int i = 0; i < k; i++) {
		int l, r;
		cin >> l >> r;
		l--;  // pasar a indexación desde cero
		r--;
		diff[l]++;
		diff[r + 1]--;
	}
 
	int sol[1000000];
	int tot = 0;
	for (int i = 0; i < n; i++) {  // construir el arreglo de sumas de prefijos
		tot += diff[i];
		sol[i] = tot;
	}
	sort(sol, sol + n);          // ordenar para obtener la mediana
	cout << sol[n / 2] << '\n';  // imprimir la mediana
}

import java.io.*;
import java.util.*;
 
class HaybaleStacking {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int k = io.nextInt();
 
		// differenceArray[n] es la diferencia entre A[n + 1] y A[n]
		int[] differenceArray = new int[n + 1];
		// leer la entrada y construir differenceArray
		for (int x = 0; x < k; x++) {
			int a = io.nextInt() - 1;  // leer y pasar a indexación desde cero
			int b = io.nextInt() - 1;
 
			differenceArray[a]++;
			differenceArray[b + 1]--;
		}
 
		int[] prefixSum = new int[n + 1];
		int total = 0;
		for (int x = 0; x < n; x++) {  // construir el arreglo prefixSum
			total += differenceArray[x];
			prefixSum[x] = total;
		}
 
		Arrays.sort(prefixSum);
		io.println(prefixSum[prefixSum.length / 2]);
		io.close();
	}
 
	// CodeSnip{Kattio}
}

n, k = map(int, input().split())
differences = [0] * (n + 1)  # crear un arreglo de diferencias
for i in range(k):
	start, end = map(int, input().split())
	# sumar uno al inicio
	differences[start - 1] += 1
	# restar uno del siguiente número fuera de start - end
	differences[end] -= 1
 
pref = [0] * n  # arreglo de sumas de prefijos
s = 0
# usa diferencias y la suma total para saber dónde están todos los fardos
for i in range(n):
	pref[i] = differences[i] + s
	s += differences[i]
pref.sort()
 
print(pref[n // 2])