#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN=105;

struct Node
{
	int in,out;
}tr[MAXN];

bool operator < (Node a,Node b)
{
	return a.in<b.in||(a.in==b.in&&a.out<b.out);
}

int n,m,re;

int d[MAXN];
void greed()
{
	for(int i=0;i<n;i++)
	{
		d[i]=1;
		for(int j=0;j<i;j++)
			if (tr[j].in<=tr[i].in&&tr[j].out<tr[i].out&&d[j]+1>d[i])
			{
				d[i]=d[j]+1;
				if (d[i]>re)
					re=d[i];
			}
	}
}

int q[MAXN],ps=0,pt=0;
int stack[MAXN],top;

inline void out(const int &dep)
{
	stack[top++]=ps;
	for(int i=ps;i<pt;i++)
		if (tr[q[i]].out<=tr[dep].in)
			ps++;
		else break;
}

inline void in(const int &dep)
{
	ps=stack[--top];
}

inline bool can(const int &dep)
{
	if (pt-ps>=m)
		return false;
	if (pt-ps==0)
		return true;
	if (tr[dep].out>=tr[q[pt-1]].out) return true;
	else return false;
}

inline void push(const int &dep)
{
	q[pt++]=dep;
}

inline void pop(const int &dep)
{
	pt--;
}

bool used[MAXN];
void search(int dep,int t)
{
	if (n-dep+t<=re)
		return ;
	if (dep==n)
	{
		re=t;
		return ;
	}
	out(dep);
	used[dep]=false;
	search(dep+1,t);
	if (can(dep))
	{
		push(dep);
		used[dep]=true;
		search(dep+1,t+1);
		pop(dep);
		used[dep]=false;
	}
	in(dep);
}

int main()
{
	freopen("train.in","r",stdin);
	freopen("train.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%d%d",&tr[i].in,&tr[i].out);
	sort(tr,tr+n);
	greed();
	search(0,0);
	printf("%d\n",re);
	return 0;
}