#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int N;
int M;
int reg[214514];
vector<int> regs[214514];
vector<int> dels[214514];

const LL INF = 0x3fffffffff;

struct LazySeg {
  int size;
  vector<char> has_lazy;
  vector<LL> seg;
  vector<LL> lazy;
  vector<LL> width;
  vector<LL> assi;

  LazySeg(vector<LL> A) {
    int n = A.size();
    size = 1;
    while (size < n) size *= 2;

    seg.resize(size);
    seg.insert(seg.end(), A.begin(), A.end());
    seg.resize(size*2);
    lazy.resize(size*2);
    has_lazy.resize(size*2);
    width.resize(size*2);
    assi.resize(size*2);
    rrep(i, size) {
      seg[i] = max(seg[i*2], seg[i*2+1]);
      width[i] = width[i*2] + width[i*2+1]; 
    }
  }

  void LazyPropagate(int k) {
    if (has_lazy[k]) {
      seg[k] = assi[k];
      if (k < size) {
        has_lazy[k*2] = true;
        has_lazy[k*2+1] = true;
        assi[k*2] = assi[k]; 
        assi[k*2+1] = assi[k];
        lazy[k*2] = 0;
        lazy[k*2+1] = 0;
      }
      has_lazy[k] = false;
    }

    seg[k] += lazy[k];
    if (k < size) {
      lazy[k*2] += lazy[k];
      lazy[k*2+1] += lazy[k];
    }
    lazy[k] = 0;
  }

  void Add(int wishl, int wishr, int k, int watchl, int watchr, LL x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }

    if (wishl <= watchl && watchr <= wishr) {
      lazy[k] += x;
      LazyPropagate(k);
      return;
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    Add(wishl, wishr, k*2, watchl, mid, x);
    Add(wishl, wishr, k*2+1, mid, watchr, x);
    seg[k] = max(seg[k*2], seg[k*2+1]);
  }

  void Move(int wishl, int wishr, int k, int watchl, int watchr, LL x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }

    if (wishl <= watchl && watchr <= wishr) {
      has_lazy[k] = true;
      lazy[k] = 0;
      assi[k] = x;
      LazyPropagate(k);
      return;
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    Move(wishl, wishr, k*2, watchl, mid, x);
    Move(wishl, wishr, k*2+1, mid, watchr, x);
    seg[k] = max(seg[k*2], seg[k*2+1]);
  }

  void Add(int wishl, int wishr, LL x) {
    return Add(wishl, wishr, 1, 0, size, x);
  }

  void Move(int wishl, int wishr, LL x) {
    return Move(wishl, wishr, 1, 0, size, x);
  }

  LL Get(int wishl, int wishr, int k, int watchl, int watchr) {
    LL lval, rval;

    if (wishr <= watchl || watchr <= wishl) return -INF;

    if (wishl <= watchl && watchr <= wishr) {
      LazyPropagate(k);
      return seg[k];
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    lval = Get(wishl, wishr, k*2, watchl, mid);
    rval = Get(wishl, wishr, k*2+1, mid, watchr);
    return max(lval, rval);
  }

  LL Get(int wishl, int wishr) {
    return Get(wishl, wishr, 1, 0, size);
  }
};


int main() {
  scanf("%d%d", &N, &M);

  vector<int> es;
  vector<pii> ps;
  rep(i, N) {
    int l, r;
    scanf("%d%d", &l, &r);
    ps.eb(pii(l, r));
  } 
  sort(all(ps));
  rep(i, N) {
    int l, r;
    auto &pa = ps[i];
    tie(l, r) = pa;
    int p = l+1;
    int q = r;
    if (p <= q) {
      es.eb(p);
      es.eb(q);
      regs[p].eb(i);
      dels[q].eb(i);
    }
  }
  sort(all(es));
  es.erase(unique(all(es)), es.end());

  LazySeg seg(vector<LL>(N, -INF/2));
  
  LL ans = 0;
  MX(ans, LL(N-M));
  int cnt = 0;
  for (int x : es) {
    cnt += regs[x].size();
    for (int idx : regs[x]) {
      seg.Move(idx, idx+1, cnt-x);
    }

    MX(ans, x + seg.Get(0, N) - M);

    cnt -= dels[x].size();
    for (int idx : dels[x]) {
      seg.Add(idx, N, -1);
      seg.Move(idx, idx+1, -INF/2);
    }
  }
  printf("%lld\n", ans);
}


Measured memory_bytes: 39276