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

struct node
{
	int l,r;
};

const int N=1e5+5;
const int K=105;

node a[N];

bool cmp(node a,node b)
{
	if(a.l!=b.l)
		return a.l<b.l;
	return a.r>b.r;
}

int dp[N][K],s[N][K];
deque <int> q[N];

inline int val(int i,int j)
{
	return dp[i][i-j]-a[i].r;
}

int main()
{
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=n;i++)
		scanf("%d %d",&a[i].l,&a[i].r);

	sort(a+1,a+n+1,cmp);

	int maxr=0,cnt=0;
	for(int i=1;i<=n;i++)
		if(a[i].r>maxr)
			maxr=a[i].r, a[++cnt]=a[i];
	k=max(0,cnt-(n-k)), n=cnt;

	dp[1][0]=s[1][0]=a[1].r-a[1].l;
	q[1].push_back(1);
	for(int i=2;i<=n;i++)
	{
		int l=1,r=i-1,maxr=0;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(a[mid].r<=a[i].l)
				maxr=mid,l=mid+1;
			else
				r=mid-1;
		}

		for(int j=0;j<=min(i-1,k);j++)
		{
			dp[i][j]=a[i].r-a[i].l;
			if(maxr>=i-j-1)
				dp[i][j]=s[maxr][maxr-(i-j-1)]+a[i].r-a[i].l;

			while(q[i-j-1].size() && q[i-j-1].front()<=maxr)
				q[i-j-1].pop_front();

			if(q[i-j-1].size())
				dp[i][j]=max(dp[i][j],val(q[i-j-1].front(),i-j-1)+a[i].r);
		}

		for(int j=0;j<=min(i-1,k);j++)
		{
			s[i][j]=dp[i][j];
			if(j)
				s[i][j]=max(s[i][j],s[i-1][j-1]);

			while(q[i-j].size() && val(q[i-j].back(),i-j)<val(i,i-j))
				q[i-j].pop_back();
			q[i-j].push_back(i);
		}
	}

	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=min(i-1,k);j++)
			if(j+n-i>=k)
				ans=max(ans,dp[i][j]);

	printf("%d\n",ans);
	return 0;
}