#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <class S, S (*op)(S, S), S (*e)()>
struct Segtree {
  int _n, size, log;
  vector<S> d;
  void update(int k) {
    d[k] = op(d[2 * k], d[2 * k + 1]);
  }
  int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
  }

  Segtree(int n) : Segtree(vector<S>(n, e())) {
  }
  Segtree(const vector<S>& v) : _n(int(v.size())) {
    log = ceil_pow2(_n);
    size = 1 << log;
    d = vector<S>(2 * size, e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i >= 1; i--) {
      update(i);
    }
  }
  void set(int p, S x) {
    p += size;
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  S get(int p) {
      return d[p+size];
  }
  S prod(int l, int r) {
    S sml = e(), smr = e();
    l += size;
    r += size;
    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }
    return op(sml, smr);
  }
};

struct S {
    int dif;
    int min;
};

S op(S l, S r) {
    S s;
    s.dif = l.dif + r.dif;
    s.min = min(l.min, l.dif+r.min);
    return s;
}

constexpr int INF = 40000;
S e() { return {0, INF}; }

int main() {
    int n, k; cin >> n >> k;
    vector<int> x;
    x.reserve(n*2);
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        a[i] = a[i]*2, b[i] = b[i]*2+1;
        x.push_back(a[i]);
        x.push_back(b[i]);
    }
    x.push_back(-2000000);
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    int m = ssize(x);
    vector<vector<int>> rl(m);
    for(int i = 0; i < n; i++) {
        int l = lower_bound(x.begin(), x.end(), a[i]) - x.begin();
        int r = lower_bound(x.begin(), x.end(), b[i]) - x.begin();
        rl[r].push_back(l);
    }
    using Seg = Segtree<S, op, e>;
    vector iv(m, S(0, 0));
    iv[0].dif = INF;
    iv[m-1].dif = -INF;
    vector dp(k+1, Seg(iv));
    auto add = [&](Seg& seg, int l, int r, int x) {
        assert(l-1 >= 0);
        S s0 = seg.get(l-1);
        s0.dif += x;
        S s1 = seg.get(r-1);
        s1.dif -= x;
        seg.set(l-1, s0);
        seg.set(r-1, s1);
    };
    auto get = [&](Seg& seg, int i) {
        return seg.prod(0, i).dif;
    };
    for(int i = 1; i < m; i++) {
        for(int j = k-1; j >= 0; j--) {
            int x = dp[j].prod(0, i).min;
            int y = get(dp[j+1], i);
            if(y > x) {
                add(dp[j+1], i, i+1, x-y);
            }
        }
        for(int j = 0; j <= k; j++) {
            for(int l : rl[i]) {
                add(dp[j], l, i, 1);
            }
        }
        cerr << x[i] << endl;
        for(int j = 0; j <= k; j++) {
            for(int kk = 0; kk < m; kk++) {
                S s = dp[j].get(kk);
                cerr << "{" << s.dif << "," << s.min << "}";
            }
            cerr << endl;
        }
        cerr << "=============" << endl;
    }
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << n - dp[k].prod(0, m).min << '\n';
}