#include <bits/stdc++.h>

using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n,m; 
	cin >> n >> m;
	vector <pair<int,int>  > a(n+1);
	vector <int> mx(n+1);
	for (int i=1;i<=n;i++) cin >> a[i].first >> a[i].second;
	sort(a.begin()+1,a.end());
	for (int i=1;i<=n;i++) mx[i]=max(mx[i-1],a[i].second);
	vector <vector<int>  > dp(n+1,vector<int>(m+1));
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			int cnt=0;
			for (int k=i;k>=1;k--){
				if (mx[k] < a[i].first)
					break;
				if (a[i].first <= a[k].second)
					cnt++;
				dp[i][j]=max(dp[i][j],dp[k-1][j-1]+cnt);
			}
		//	cout << dp[i][j] << " ";
		}
		//cout << "\n";
	}
	cout << dp[n][m] << "\n";
}