#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define pb push_back
#define mp make_pair
#define READS(x); string x;cin >> x;
#define READ(x); int x;cin >> x;
#define DOUREAD(x,y); int x,y;cin >> x >> y;
#define TRIREAD(x,y,z); int x,y,z;cin >> x >> y >> z;
const int MAXN = 1e5+69;
int n, m, k, L[MAXN], R[MAXN], dp[MAXN], p[MAXN], dq[MAXN];
vector<int> vals, seg[MAXN];
int st[4*MAXN],lz[4*MAXN];
#define tm ((tl + tr) >> 1)
#define left id << 1, tl, tm
#define right id << 1 | 1, tm + 1, tr
void build(int id = 1, int tl = 0, int tr = m - 1) {
	if(tl == tr) st[id] = dq[tl], lz[id] = 0;
	else{
	   int mid = (tl+tr)>>1;
		build(2*id,tl,mid);
		build(2*id+1,mid+1,tr);
		st[id] = min(st[2*id], st[2*id+1]);
		lz[id] = 0;
	}
}
void apply(int id, int v) {
	st[id] += v;
	lz[id] += v;
}
void push(int id){
	if(lz[id]){
	   apply(2*id, lz[id]);
	   apply(2*id+1, lz[id]);
	}
	lz[id] = 0;
}
void update(int l, int r, int v, int id = 1, int tl = 0, int tr = m - 1) {
	if (l > tr || tl > r) return ;
	if (l <= tl && tr <= r) return apply(id, v);
	push(id);
	update(l, r, v, left);
	update(l, r, v, right);
	st[id] = min(st[2*id], st[2*id+1]);
}
int query(int l, int r, int id = 1, int tl = 0, int tr = m - 1) {
	if (l > tr || tl > r) return 1e9;
	if (l <= tl && tr <= r) return st[id];
	return push(id), min(query(l, r, left), query(l, r, right));
}
signed main(){fast
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> L[i] >> R[i];
		vals.pb(L[i]);
		vals.pb(R[i]);
	}
	sort(vals.begin(), vals.end());
	vals.resize(m = unique(vals.begin(), vals.end()) - vals.begin());
	for (int i = 1; i <= n; i++) {
		L[i] = lower_bound(vals.begin(), vals.end(), L[i]) - vals.begin() + 1;
		R[i] = lower_bound(vals.begin(), vals.end(), R[i]) - vals.begin() + 1;
		seg[R[i]].pb(L[i]);
	}
	m++;
	for (int i = 1; i <= n; i++) p[L[i]] ++;
	for (int i = 1; i <= m ; i++) p[i] += p[i-1];
	memset(dq, 0x3f, sizeof dq);
	dq[0] = 0;
	int ans = 0;
	while(k--){
		build();
		//1..x..[j....i] => dp(k,x)++
		//dp(k,i) -> min dp(k-1,j)
		//ans = max # - dp(k,i)
		for(int i = 0; i < m; i++){
			for(int j : seg[i]) update(0, j-1, 1);
			dp[i] = query(0, i);
			ans = max(ans, p[i] - dp[i]);
		}
		for(int i = 0; i < m; i++) dq[i] = dp[i];
	}
	cout << ans << '\n';
}