#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, int 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;
}