#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m, ans, cnt;
struct data {
  int l, r;
} ordl[N], ordr[N];
bool cmpl(data a, data b) { return a.l < b.l; }
bool cmpr(data a, data b) { return a.r < b.r; }
struct node {
  int mx, tag;
} t[N << 2];
void puttag(int x, int val) {
  t[x].mx += val;
  t[x].tag += val;
}
void push_down(int x) {
  puttag(x << 1, t[x].tag);
  puttag(x << 1 | 1, t[x].tag);
  t[x].tag = 0;
}
void push_up(int x) { t[x].mx = max(t[x << 1].mx, t[x << 1 | 1].mx); }
void modify(int l, int r, int val, int x = 1, int lp = 1, int rp = n) {
  if (l > rp || r < lp) return;
  if (lp >= l && rp <= r) {
    puttag(x, val);
    return;
  }
  if (t[x].tag) push_down(x);
  int mid = (lp + rp) >> 1;
  modify(l, r, val, x << 1, lp, mid);
  modify(l, r, val, x << 1 | 1, mid + 1, rp);
  push_up(x);
}
int query(int l, int r, int x = 1, int lp = 1, int rp = n) {
  if (l > rp || r < lp) return 0;
  if (lp >= l && rp <= r) return t[x].mx;
  if (t[x].tag) push_down(x);
  int mid = (lp + rp) >> 1;
  return max(query(l, r, x << 1, lp, mid),
             query(l, r, x << 1 | 1, mid + 1, rp));
}
int main() {
  int a, b;
  scanf("%d%d", &n, &m);
  ans = max(0, n - m);
  cnt = n;
  for (int i = 1; i <= cnt; ++i) {
    scanf("%d%d", &a, &b);
    a++;
    b--;
    if (a > b) {
      i--, cnt--;
      continue;
    }
    ordl[i] = (data){a, b};
    ordr[i] = (data){a, b};
  }
  sort(ordl + 1, ordl + cnt + 1, cmpl);
  sort(ordr + 1, ordr + cnt + 1, cmpr);
  int pl = 1, pr = 1;
  for (int i = 1; i <= n; ++i) {
    modify(1, i, 1);
    for (; ordl[pl].l <= i && pl <= cnt; ++pl) modify(ordl[pl].l, n, 1);
    ans = max(ans, query(1, i) - m);
    for (; ordr[pr].r <= i && pr <= cnt; ++pr) modify(ordr[pr].l, n, -1);
  }
  printf("%d\n", ans);
  return 0;
}
