#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<int>p;
int l[500005],r[500005],len[500005];
int a[500005],b[500005];
int dp[100005][101][2];
bool cmp(int a,int b){
	if(l[a] == l[b])return r[a]>r[b];
	return l[a]<l[b];
}int ok[200005];
signed main(){
	cin >> n>> k;
	for(int i = 1;i<=n;i++){
		cin >> l[i] >> r[i];len[i] = r[i]-l[i]+1;p.push_back(i);
	}sort(p.begin(),p.end(),cmp);
	vector<pair<int,int> >p1;p1.push_back({-1,-1});
	int tot = 0;vector<int>pp;
	for(int i =0;i<p.size();i++){
	//	cout << l[p[i]] << "  " << r[p[i]] << endl;
		if(l[p[i]]>p1.back().second){
			tot++;p1.push_back({l[p[i]],r[p[i]]});ok[p[i]] = 1;
			pp.clear();pp.push_back(p[i]);
		}else{
			if(r[p[i]]>p1.back().second){
				p1.back().second = r[p[i]];
				if(pp.size() == 1)tot++,pp.push_back(p[i]),ok[p[i]] = 1;
				else{
		//			cout << r[pp[pp.size()-2]] <<"  " << l[p[i]] << endl;
					if(r[pp[pp.size()-2]]>=l[p[i]]){
						ok[pp.back()] = 0;pp.pop_back();pp.push_back(p[i]);ok[p[i]] = 1;
					}else tot++,pp.push_back(p[i]),ok[p[i]] = 1;
				}
			}//else if(pp.size()>1 and r[p[i]] == p1.back().second and len[p[i]]>len[pp.back()]){
			//	ok[pp.back()] = 0;pp.pop_back();pp.push_back(p[i]);ok[p[i]] = 1;
			//}
		}
	}int sum = 0;
//	cout << tot << endl;
	vector<pair<int,int> >seg;
	for(int i =0;i<p.size();i++){
		if(ok[p[i]]){
			seg.push_back({l[p[i]],r[p[i]]});
		}
	}for(int i =0;i<p1.size();i++){
		sum+=p1[i].second-p1[i].first;
	}for(int i =0;i<seg.size();i++){
		int mx = seg[i].first,mn = seg[i].second;
	//	cout << mx << " " << mn << endl;
		if(i!=0)mx =max(mx,seg[i-1].second);
		if(i!=seg.size()-1)mn = min(mn,seg[i+1].first);
		a[i+1] = mn-mx;
	}
	for(int i =1;i<seg.size();i++){
		int dis = max((int)0,seg[i-1].second-seg[i].first);
		b[i+1] = dis;
	}//for(int i =1;i<=seg.size();i++)cout << a[i] << ' ';cout << endl;
	//for(int i = 2;i<=seg.size();i++)cout << b[i] << " ";cout << endl;
	//cout << sum << endl;
	if(n-tot>=k){
		cout << sum << '\n';return 0;
	}memset(dp,63,sizeof(dp));
	dp[0][0][0] = 0;k -= n-tot;
	for(int i = 1;i<=seg.size();i++){
		for(int j =0;j<=k;j++){
			dp[i][j][0] = min(dp[i-1][j][1],dp[i-1][j][0]);
			if(j)dp[i][j][1] = min(dp[i-1][j-1][1]+a[i]+b[i],dp[i-1][j-1][0]+a[i]);
		//	cout << i << " " << dp[i-1][j-1][1]+a[i]+b[i] <<" " << dp[i-1][j-1][0]+a[i] << endl;
		}//cout << endl;
	}int ans = min(dp[seg.size()][k][0],dp[seg.size()][k][1]);
	cout << sum-ans << endl;return 0;
}/*
7 4
1 3 2 5 3 4
6 8 9 17 10 16
18 20 
*/