#include<bits/stdc++.h>
#define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i = ll(j)-1; i >= ll(k); i--)
#define rrep(i,k) rrep2(i,k,0)
#define eb emplace_back
#define SZ(a) ll(a.size())
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX/4;
bool chmin(auto& a, auto b) {return a>b ? a=b, 1 : 0;}
bool chmax(auto& a, auto b) {return a<b ? a=b, 1 : 0;}

template<typename T = ll, typename S = ll>
struct lazy_segment_tree {
	ll n;
	ll LOG;
	vector<T> node;
	vector<S> lazy;
	T vINF;
	S lINF;
	lazy_segment_tree(vl x, T vINF_, S lINF_){
		vINF = vINF_;
		lINF = lINF_;
		n = 1;
		LOG = 1;
		while(n <= x.size()) n *= 2, LOG++;
		node.resize(2*n, vINF);
		lazy.resize(2*n, lINF);
		rep(i,SZ(x)) node[i+n] = x[i];
		rrep(i,n) node[i] = compare(node[i*2], node[i*2+1]);
	}
	T compare(T l, T r){
		return max(l,r);
	}
	T add1(T l, S r){
		return l+r;
	}
	S add2(S l, S r){
		return l+r;
	}

	void eval(ll idx){
		node[idx] = add1(node[idx], lazy[idx]);
		if(idx < n){
			lazy[idx*2] = add2(lazy[idx*2], lazy[idx]);
			lazy[idx*2+1] = add2(lazy[idx*2+1], lazy[idx]);
		}
		lazy[idx] = lINF;
	}

	void update(ll idx, T val){
		ll now = idx + n;
		rrep(i,LOG+1) eval(now>>i);
		node[now] = val;
		while(now > 0){
			now >>= 1;
			node[now] = compare(node[now*2], node[now*2+1]);
		}
	}

	void add(ll l, ll r, S val, ll now = -1, ll left = 0, ll right = -1){
		if(now == -1){
			now = 1;
			right = n;
		}
		eval(now);
		if(l <= left && right <= r){
			lazy[now] = add2(lazy[now], val);
			return;
		}
		if(r <= left || right <= l) return;
		ll mid = (left+right)/2;
		add(l, r, val, now*2, left, mid);
		add(l, r, val, now*2+1, mid, right);
	}

	T calc(ll l, ll r, ll now = -1, ll left = 0, ll right = -1){
		if(now == -1){
			now = 1;
			right = n;
		}
		eval(now);
		if(l <= left && right <= r) return node[now];
		if(r <= left || right <= l) return vINF;
		ll mid = (left+right)/2;
		return compare(calc(l,r,now*2,left,mid), calc(l,r,now*2+1,mid,right));
	}
};

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	ll n,k; cin >> n >> k;
	vl l(n), r(n);
	rep(i,n) cin >> l[i] >> r[i];
	ll m = 0;
	{
		map<ll,ll> mem;
		rep(i,n){
			mem[l[i]] = 0;
			mem[r[i]+1] = 0;
		}
		for(auto &el: mem) el.second = m++;
		rep(i,n){
			l[i] = mem[l[i]]+1;
			r[i] = mem[r[i]+1]+1;
		}
	}
	vvl add(m+2), left(m+2);
	rep(id,n){
		add[l[id]].eb(1);
		left[l[id]].eb(l[id]);
		add[r[id]+1].eb(-1);
		left[r[id]+1].eb(l[id]);
	}
	vvl dp(m+1, vl(k+1));
	vector<lazy_segment_tree<ll,ll>> seg(k, lazy_segment_tree<>(vl(m+1,0), 0ll, 0ll));
	rep(i,m){
		rep(id,SZ(add[i+1])){
			rep(j,k) seg[j].add(0, left[i+1][id], add[i+1][id]);
		}
		rep(j,k){
			dp[i+1][j+1] = seg[j].calc(0,i+1);
			/*
			rep(last,i+1){
				ll cnt = 0;
				rep(id,n){
					if(l[id] > last && l[id] <= i+1 && r[id] > i+1) cnt++;
				}
				chmax(dp[i+1][j+1], dp[last][j]+cnt);
			}*/
		}
		rep(j,k){
			seg[j].update(i+1, dp[i+1][j]);
		}
	}
	ll ans = 0;
	rep(i,m+1){
		rep(j,k+1) chmax(ans, dp[i][j]);
	}
	cout << ans << endl;
}