//Ilie Dumitru
#include<cstdio>
#include<algorithm>
const int NMAX=256;

struct intv
{
	int a, b;

	friend bool operator<(intv x, intv y)
	{
		return x.b<y.b || (x.b==y.b && x.a<y.a);
	}
};

int N, K;
intv v[NMAX];
int len[NMAX][NMAX];
int dp[2][NMAX][NMAX];

/*
4 3
0 100
99 101
200 300
299 301
*/

int ignore()
{
	int i, j, k, st, nst, max;

	--K;

	for(i=0;i<N;++i)
		for(j=0;j<K;++j)
			dp[0][i][j]=dp[1][i][j]=0;
	dp[0][0][0]=len[0][0];
	st=0;
	for(i=1;i<N;++i)
	{
		st=i&1;
		nst=!st;
		for(j=0;j<i;++j)
			for(k=0;k<K;++k)
				dp[st][j][k]=0;

		for(j=0;j<i;++j)
		{
			for(k=0;k<K;++k)
			{
				dp[st][j][k]=std::max(dp[st][j][k], dp[nst][j][k]-len[j][i-1]+len[j][i]);
				dp[st][j][k]=std::max(dp[st][j][k], dp[nst][j][k]-len[j][i-1]+len[j][i]);
				dp[st][i][k+1]=std::max(dp[st][i][k+1], dp[nst][j][k]+len[i][i]);
			}
		}
	}

	max=0;
	for(j=0;j<N;++j)
		for(k=0;k<K;++k)
			if(dp[st][j][k]>max)
				max=dp[st][j][k];

	++K;

	return max;
}

int main()
{
	//FILE* f=fopen("echipe.in", "r"), *g=fopen("echipe.out", "w");
	FILE* f=stdin, *g=stdout;
	int i, j, k, st, nst, max;
	intv s;

	fscanf(f, "%d%d", &N, &K);
	for(i=0;i<N;++i)
		fscanf(f, "%d%d", &v[i].a, &v[i].b);

	std::sort(v, v+N);

	for(i=0;i<N;++i)
	{
		s=v[i];
		for(j=i;j<N && s.a<s.b;++j)
		{
			if(s.a<v[j].a)
				s.a=v[j].a;
			if(s.a<s.b)
				len[i][j]=s.b-s.a;
		}
	}

	dp[0][0][0]=len[0][0];
	st=0;
	for(i=1;i<N;++i)
	{
		st=i&1;
		nst=!st;
		for(j=0;j<i;++j)
			for(k=0;k<K;++k)
				dp[st][j][k]=0;

		for(j=0;j<i;++j)
		{
			for(k=0;k<K;++k)
			{
				dp[st][j][k]=std::max(dp[st][j][k], dp[nst][j][k]-len[j][i-1]+len[j][i]);
				dp[st][i][k+1]=std::max(dp[st][i][k+1], dp[nst][j][k]+len[i][i]);
			}
		}
	}

	max=0;
	for(j=0;j<N;++j)
		for(k=0;k<K;++k)
			if(dp[st][j][k]>max)
				max=dp[st][j][k];

	if(K>1)
		max=std::max(max, ignore());

	fprintf(g, "%d\n", max);

	fclose(f);
	fclose(g);
	return 0;
}