#include "bits/stdc++.h"
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using ll = long long;
using pii = pair<int, int>;

#define int long long
const int N = 2e4 + 11;
const int P = 2e6 + 11;
int dp[P], A[N], B[N];

int n, k, ID;

int to(int i, int j){
	return i * (ID + 1) + j;
}

struct SegTree{
	int t[N << 2], lz[N << 2];
	void build(int v, int l, int r){
		t[v] = lz[v] = 0;
		if(l != r){
			int m = (l + r) / 2;
			build(v * 2 + 1, l, m);
			build(v * 2 + 2, m + 1, r);
		}
	}
	void push(int v){
		t[v * 2 + 1] += lz[v];
		t[v * 2 + 2] += lz[v];
		lz[v * 2 + 1] += lz[v];
		lz[v * 2 + 2] += lz[v];
		lz[v] = 0;
	}
	void add(int ql, int qr, int qv, int v, int l, int r){
		if(qr < l || r < ql) return;
		if(ql <= l && r <= qr) { t[v] += qv; lz[v] += qv; return; }
		else {
			int m = (l + r) / 2; push(v);
			add(ql, qr, qv, v * 2 + 1, l, m);
			add(ql, qr, qv, v * 2 + 2, m + 1, r);
			t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
		}
	}
	void upd(int qi, int qv, int v, int l, int r){
		if(l == r) { t[v] = qv; }
		else {
			int m = (l + r) / 2; push(v);
			if (qi <= m) upd(qi, qv, v * 2 + 1, l, m);
			else upd(qi, qv, v * 2 + 2, m + 1, r); 
			t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
		}
	}
	int qry_min(int ql, int qr, int v, int l, int r){
		if(qr < l || r < ql) return 1 << 30;
		if(ql <= l && r <= qr) return t[v];
		else {
			int m = (l + r) / 2;
			int a = qry_min(ql, qr, v * 2 + 1, l, m);
			int b = qry_min(ql, qr, v * 2 + 2, m + 1, r);
			return min(a, b);
		}
	}
} ST;
void solve(int TC) {
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		int a, b; cin >> a >> b;
		A[i] = a, B[i] = b;
	}
	set<int> S; map<int, int> mp;
	for(int i = 0; i < n; i++){
		S.insert(A[i]); S.insert(B[i]);
	}
	int id = 0; for(auto x : S) mp[x] = ++id;
	ID = id;
	for(int i = 0; i < n; i++){
		A[i] = mp[A[i]], B[i] = mp[B[i]];
	}

	vector<pair<int, int>> vp;
	sort(vp.begin(), vp.end(), [](auto x, auto y){
		return x.second < y.second;
	});

	fill(dp, dp + P, 1 << 30);
	dp[0] = 0;
	for(int i = 0; i < k; i++){
		int id = 0;
		ST.build(0, 0, id);
		for(int j = 1; j <= id; j++){
			while(id < vp.size() && vp[id].second < j){
				ST.add(0, vp[id].first - 1, 1, 0, 0, id);
			}
			dp[to(i, j)] = ST.qry_min(0, j - 1, 0, 0, id);
			ST.upd(j, dp[j], 0, 0, n);
		}
	}
	cout << n - dp[to(k, id)] << '\n';
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	// cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}