#include <bits/stdc++.h>
using namespace std;
struct aa {
  int l, r;
} a[200010];
struct tt {
  int l, r, f, mx;
} t[200010 * 2];
int n, m, ans, x, y, l, l1;
inline bool cmp(aa a, aa b) { return a.l < b.l; }
inline void maketree(int L, int R) {
  t[l].l = t[l].r = t[l].f = 0;
  t[l].mx = R;
  if (L < R) {
    int mid = (L + R) >> 1, l1 = l;
    l++;
    t[l1].l = l;
    maketree(L, mid);
    l++;
    t[l1].r = l;
    maketree(mid + 1, R);
  }
}
inline void pushdown(int i) {
  if (t[i].f) {
    t[t[i].l].f += t[i].f;
    t[t[i].l].mx += t[i].f;
    t[t[i].r].f += t[i].f;
    t[t[i].r].mx += t[i].f;
    t[i].f = 0;
  }
}
inline void ins(int i, int a, int b, int L, int R) {
  if (a <= L && R <= b) {
    t[i].f++;
    t[i].mx++;
    return;
  }
  pushdown(i);
  int mid = (L + R) >> 1;
  if (a <= mid) ins(t[i].l, a, b, L, mid);
  if (mid < b) ins(t[i].r, a, b, mid + 1, R);
  t[i].mx = max(t[t[i].l].mx, t[t[i].r].mx);
}
int main() {
  scanf("%d%d", &n, &m);
  ans = max(0, n - m);
  l = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &x, &y);
    if (x + 2 <= y) {
      a[++l].l = x + 1;
      a[l].r = y - 1;
    }
  }
  sort(a + 1, a + 1 + l, cmp);
  l1 = l;
  l = 1;
  maketree(1, n);
  for (int i = 1; i <= l1; i++) {
    ins(1, 1, a[i].r, 1, n);
    x = t[1].mx;
    ans = max(ans, x - a[i].l + 1 - m);
  }
  printf("%d", ans);
  return 0;
}
