#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

typedef long long ll;
typedef long double ld;
int n, k;
const int maxN = 2e4 + 10;
ll dp[maxN];
ll ndp[maxN];
const int INF = 1e9;
ll lazy[4 * maxN];
ll mn[4 * maxN];
void apply(int v, ll x) {
    lazy[v] += x;
    mn[v] += x;
}
void push(int v, int tl, int tr) {
    if (tl != tr && lazy[v] != 0) {
        apply(2 * v, lazy[v]);
        apply(2 * v + 1, lazy[v]);
    }
    lazy[v] = 0;
}
void merge(int v) {
    mn[v] = min(mn[2 * v], mn[2 * v + 1]);
}
void upd(int v, int tl, int tr, int l, int r, ll x) {
    if (tr < l || tl > r) return;
    if (l <= tl && tr <= r) {
        apply(v, x);
        return;
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    upd(2 * v, tl, tm, l, r, x);
    upd(2 * v + 1, tm + 1, tr, l, r, x);
    merge(v);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    cin >> n >> k;
    vector<int> S;
    S.emplace_back(-1e7);
    vector<pair<int,int>> ints;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        ints.emplace_back(a, b);
        S.emplace_back(a);
        S.emplace_back(b);
    }
    S.emplace_back(1e7);
    sort(S.begin(), S.end());
    S.erase(unique(S.begin(), S.end()), S.end());
    for (int p = 0; p < S.size(); p++) {
        dp[p] = INF;
    }
    vector<vector<int>> D(S.size());
    for (auto& it : ints) {
        int where = lower_bound(S.begin(), S.end(), it.second) - S.begin();
        int ps = lower_bound(S.begin(), S.end(), it.first) - S.begin();
        D[where].emplace_back(ps);
    }
    dp[0] = 0;
    k++;
    k = min(k, (int)S.size() - 1);
    for (int it = 0; it < k; it++) {
        ndp[0] = INF;
        for (int z = 0; z <= 4 * S.size() + 5; z++) {
            mn[z] = INF;
            lazy[z] = 0;
        }
        upd(1, 0, S.size() - 1, 0, 0, dp[0] -INF);
        for (int t = 1; t < S.size(); t++) {
            for (int x : D[t - 1]) {
                upd(1, 0, S.size() - 1, 0, x - 1, +1);
            }
            ndp[t] = mn[1];
            upd(1, 0, S.size() - 1, t, t, dp[t] - INF);
        }
        for (int t = 0; t < S.size(); t++) {
            dp[t] = ndp[t];
        }
    }
    cout << n - dp[S.size() - 1];

    return 0;
}