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

#define rep(i,a,b) for(int i=(int)a; i<(int)b; i++)
#define Int long long
#define int long long
#define V vector

void solve();
signed main(){
	solve();
}

#define cerr if(0) cerr

const int N = 5e5+5;
const int Z = 2*N;
const int INF = 1e9;

int n, k;
int a[N], b[N];

int z; // max zipped value
map<int,int> zip;

// dp[i][j] = min # skipped interval if we selected i value and the last one is j
// value 0 must be chosen.
V<int> dp[N];

// range add update
// range min query
// point assign update
#define mid (tl+tr)/2
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
struct Segtree{
	int st[2*Z], lz[2*Z];
	void add(int l,int r,int x,int v=0,int tl=0,int tr=z){
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r){
			st[v] += x; lz[v] += x; return;
		}
		if(lz[v]){
			add(1,n,lz[v], lc,tl,mid);
			add(1,n,lz[v], rc,mid+1,tr);
			lz[v] = 0;
		}
		add(l,r,x, lc,tl,mid);
		add(l,r,x, rc,mid+1,tr);
		st[v] = min(st[lc], st[rc]);
	}
	void assign(int i,int x,int v=0,int tl=0,int tr=z){
		if(tl==tr){
			st[v] = x; return;
		}
		if(lz[v]){
			add(1,n,lz[v], lc,tl,mid);
			add(1,n,lz[v], rc,mid+1,tr);
			lz[v] = 0;
		}
		if(i<=mid) assign(i,x, lc,tl,mid);
		else assign(i,x, rc,mid+1,tr);
		st[v] = min(st[lc], st[rc]);
	}
	int qry(int l,int r,int v=0,int tl=0,int tr=z){
		if(r<tl || tr<l) return INF;
		if(l<=tl && tr<=r) return st[v];
		if(lz[v]){
			add(1,n,lz[v], lc,tl,mid);
			add(1,n,lz[v], rc,mid+1,tr);
			lz[v] = 0;
		}
		return min({
			qry(l,r, lc,tl,mid),
			qry(l,r, rc,mid+1,tr)
		});
	}
} segtree;


V<int> endHere[Z];

void solve(){
	cin >> n >> k;

	rep(i,1,n+1){
		cin >> a[i] >> b[i];
		zip[a[i]];
		zip[b[i]];
	}

	// compress value
	zip[-INF];
	zip[INF];
	z = -1;
	for(auto&[x,y] : zip) y = ++z;
	cerr << "z: " << z << endl;

	rep(i,1,n+1){
		a[i] = zip[a[i]];
		b[i] = zip[b[i]];

		// cerr << "ab[i] " << a[i] << " " << b[i] << endl;
		endHere[b[i]].push_back(a[i]);
	}

	dp[1] = V<int>(z+1, INF);
	dp[1][0] = 0;

	rep(i,2,k+3){
		dp[i] = V<int>(z+1);
		// cerr << "i: " << i << endl;

		// insert previous raw dp values into segtree
		for(int x=0; x<=z; x++){
			segtree.assign(x, dp[i-1][x]);
		}

		// calculate current dp
		for(int x=0; x<=z; x++){
			// dp[i][x] = min(dp[i][x], dp[i-1][y] + #skippedInterval)
			dp[i][x] = segtree.qry(0,x);
			// cerr << dp[i][x] << " ";

			for(int y : endHere[x]){
				segtree.add(0,y-1, 1);
			}
		}
		cerr << endl;
	}

	cerr << "n: " << n << endl;
	cerr << "dp[k+2][z]: " << dp[k+2][z] << endl;
	int ans = n - dp[k+2][z];
	cout << ans << '\n';



}