#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9 + 10;
const int maxn = 1e6 + 200;
const int mod = 1e9 + 7;
const double eps = 1e-9;
int dcmp(double x) {
  if (fabs(x) < eps) return 0;
  return x < 0 ? -1 : 1;
}
long long powmod(long long x, long long n) {
  long long ret = 1;
  for (; n > 0; n >>= 1, x = x * x % mod)
    if (n & 1) ret = ret * x % mod;
  return ret;
}
int sz;
struct SegTree {
  int lazy[maxn << 2], mx[maxn << 2];
  void push(int rt) {
    if (lazy[rt] == 0) return;
    lazy[(rt << 1)] += lazy[rt], lazy[(rt << 1 | 1)] += lazy[rt];
    mx[(rt << 1)] += lazy[rt], mx[(rt << 1 | 1)] += lazy[rt];
    lazy[rt] = 0;
  }
  void maintain(int rt) { mx[rt] = max(mx[(rt << 1)], mx[(rt << 1 | 1)]); }
  void build(int l, int r, int rt) {
    lazy[rt] = 0;
    if (l == r)
      mx[rt] = -(sz - l);
    else {
      int mid = l + r >> 1;
      build(l, mid, (rt << 1));
      build(mid + 1, r, (rt << 1 | 1));
      maintain(rt);
    }
  }
  void update(int l, int r, int rt, int ql, int qr, int v) {
    if (ql <= l && qr >= r) {
      lazy[rt] += v;
      mx[rt] += v;
    } else {
      push(rt);
      int mid = l + r >> 1;
      if (ql <= mid) update(l, mid, (rt << 1), ql, qr, v);
      if (qr > mid) update(mid + 1, r, (rt << 1 | 1), ql, qr, v);
      maintain(rt);
    }
  }
  int query(int l, int r, int rt, int ql, int qr) {
    if (ql <= l && qr >= r) return mx[rt];
    int mid = l + r >> 1, mx = (int)-1e9;
    if (ql <= mid) mx = query(l, mid, (rt << 1), ql, qr);
    if (qr > mid) mx = max(mx, query(mid + 1, r, (rt << 1 | 1), ql, qr));
    return mx;
  }
} Tree;
pair<int, int> seg[maxn];
int n, m;
bool check(int L) {
  for (int i = 1; i <= m; ++i) seg[i].second += L;
  sz = n + L;
  Tree.build(1, sz, 1);
  for (int i = 1, p = 1; i <= sz; ++i) {
    while (p <= m && seg[p].second <= i) {
      if (seg[p].first <= seg[p].second)
        Tree.update(1, sz, 1, 1, seg[p].first, 1);
      ++p;
    }
    int now = Tree.query(1, sz, 1, 1, i) + (sz - i) - 1;
    if (now > 0) {
      for (int i = 1; i <= m; ++i) seg[i].second -= L;
      return 0;
    }
  }
  for (int i = 1; i <= m; ++i) seg[i].second -= L;
  return 1;
}
bool work() {
  cin >> n >> m;
  swap(n, m);
  int res = 0;
  for (int i = (int)(1); i <= (int)(m); ++i) {
    cin >> seg[i].first >> seg[i].second;
    seg[i].first += n;
    swap(seg[i].first, seg[i].second);
    if (seg[i].first > seg[i].second) res++;
    seg[i].second -= n;
  }
  sort(seg + 1, seg + m + 1,
       [](const pair<int, int> &a, const pair<int, int> &b) {
         return a.second < b.second;
       });
  int l = n, r = n + m;
  if (res) l++;
  while (l < r) {
    int mid = l + r >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << l - n << '\n';
  return 0;
}
int main() {
  srand(time(NULL));
  ios::sync_with_stdio(0), cin.tie(0);
  double c = clock();
  int T = 2e6;
  while (T--) {
    if (!work()) {
      break;
    }
  }
  return 0;
}
