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

const int maxn = 510000;

int n,K;
struct node
{
	int l,r;
}a[maxn];

int t[maxn],tp;
map<int,int>mp; int mpn;

short int num[20005][20005];

vector<int>f[maxn];

void solve(int k,int ml,int mr,int l,int r)
{
	if(l>r) return;
	int mid=(l+r)>>1;
	int mi,ma=n+1;
	for(int i=ml;i<=mr;i++) if(i<mid)
	{
		int temp= f[k-1][i]+ (int)num[i+1][mid-1];
		if(temp<ma)
		{
			ma=temp;
			mi=i;
		}
	}
	f[k][mid]=ma;
	solve(k,ml,mi,l,mid-1);
	solve(k,mi,mr,mid+1,r);
}

int main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n>>K;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].l>>a[i].r;
		t[++tp]=a[i].l;
		t[++tp]=a[i].r;
	}
	
	sort(t+1,t+tp+1);
	for(int i=1;i<=tp;i++)
	{
		if(i==1||t[i]!=t[i-1]) mp[t[i]]=++mpn;
	}
	for(int i=1;i<=n;i++) 
	{
		a[i].l=mp[a[i].l];
		a[i].r=mp[a[i].r];
	}
	
	for(int i=1;i<=n;i++) num[a[i].l][a[i].r]++;
	for(int l=mpn;l>=1;l--)
	{
		for(int r=l;r<=mpn;r++)
		{
			num[l][r]+=num[l][r-1];
		}
		for(int r=l;r<=mpn;r++)
		{
			num[l][r]+=num[l+1][r];
		}
	}
	
	f[1].resize(mpn+5);
	for(int r=1;r<=mpn;r++)
	{
		f[1][r]=num[1][r-1];
	}
	for(int i=2;i<=K;i++)
	{
		f[i].resize(mpn+5);
		solve(i,1,mpn,1,mpn);
	}
	int ans=n;
	for(int i=K;i<=mpn;i++) ans=min(ans,f[K][i]+num[i+1][mpn]);
	cout<<n-ans<<endl;
	
	return 0;
}