#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[2020],b[2020],res[2010];
set<array<int,3> > s;
vector<pair<int,int> > e[2010];
int f[2010][2],cnt[2010][2];// f i j k / i 的子树，k=0/1 i 是否选 
int vis[2010];
void dfs0(int u){
	vis[u]=1;
	for(int i=0;i<(int)e[u].size();i++){
		int v=e[u][i].second;
		if(vis[v]) continue;
		dfs0(v);
	}
}
pair<int,int> upd(int f1,int c1,int f2,int c2){
	if(f1>f2){
		return {f2,c2};
	}
	else if(f1<f2){
		return {f1,c1};
	}
	return {f1,min(c1,c2)};
}
void dfs1(int u,int fa,int at){
	f[u][0]=0;
	cnt[u][0]=0;
	if(u!=0){
		f[u][1]=res[u]+at;
		cnt[u][1]=1;
	}
	else{
		f[u][1]=1ll<<60;
		cnt[u][1]=0;
	}
	for(int i=0;i<(int)e[u].size();i++){
		int v=e[u][i].second,w=e[u][i].first;
		if(v==fa) continue;
		dfs1(v,u,at);
	/*	f[u][0]=min(f[u][0]+f[v][0],f[u][0]+f[v][1]);
		f[u][1]=min(f[u][1]+f[v][0],f[u][1]+f[v][1]-w);*/
		tie(f[u][0],cnt[u][0])=upd(f[u][0]+f[v][0],cnt[u][0]+cnt[v][0],f[u][0]+f[v][1],cnt[u][0]+cnt[v][1]);
		tie(f[u][1],cnt[u][1])=upd(f[u][1]+f[v][0],cnt[u][1]+cnt[v][0],f[u][1]+f[v][1]-w,cnt[u][1]+cnt[v][1]);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		s.insert({a[i],i,0});
		s.insert({b[i],i,1});
	}
	for(auto it=s.begin();it!=s.end();it++){
		if(it==prev(s.end())) break;
		auto u=*it,v=*next(it);
		if(u[2]==0&&v[2]==1){
			int w=v[0]-u[0];
			e[u[1]].push_back({w,v[1]});
			e[v[1]].push_back({w,u[1]});
//			cerr<<"edge: "<<u[1]<<" "<<v[1]<<" "<<w<<"\n";
		}
		if(u[2]==0) res[u[1]]+=v[0]-u[0];
		if(v[2]==1) res[v[1]]+=v[0]-u[0];
	}
/*	for(int i=1;i<=n;i++){
		cout<<res[i]<<"\n";
	}*/
	vector<int> re;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs0(i);
			re.push_back(i);
		}
	}
	for(int i=0;i<(int)re.size();i++){
		e[0].push_back({0,re[i]});
		e[re[i]].push_back({0,0});
//		cerr<<"edge: "<<0<<" "<<re[i]<<"\n";
	}
	int need=n-k;
	int le=-1e9,ri=1e9,mid;
	while(le<ri){
		mid=(le+ri)>>1;
		memset(f,0,sizeof(f));
		memset(cnt,0,sizeof(cnt));
//		cerr<<le<<" "<<ri<<" "<<mid<<"\n";
		dfs1(0,-1,mid);
		int ans,cs;
		tie(ans,cs)=upd(f[0][0],cnt[0][0],f[0][1],cnt[0][1]);
//		for(int i=0;i<=n;i++){
//			cerr<<"ch:"<<i<<" "<<f[i][0]<<" "<<cnt[i][0]<<" "<<f[i][1]<<" "<<cnt[i][1]<<"\n";
//		}
//		cout<<ans<<" "<<cs<<"\n";
		if(cs<=need) ri=mid;
		else le=mid+1;
	}
	dfs1(0,-1,le);
	int ans,cs;
	tie(ans,cs)=upd(f[0][0],cnt[0][0],f[0][1],cnt[0][1]);
//	cerr<<le<<" "<<ans<<" "<<cs<<"\n";
	cout<<ans-le*need<<"\n";
}