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

int n,k;
struct node{
	int a,b;
}book[210];
int diff[210];
int dp[210];
int ans=0;
int ansc=0;

bool cmp(node g,node h){
	return g.a<h.a;
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>book[i].a>>book[i].b;
	}
	sort(book+1,book+1+n,cmp);
	int frt;
	frt=book[1].b;
	diff[1]=0;diff[n+1]=0;
	for(int i=2;i<=n;i++){
        diff[i]=book[i].b-frt;
        frt=book[i].b;//
        ansc+=abs(diff[i]);
	}
    memset(dp,-1,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++){
        for(int j=min(k,i);j>=1;j--){
            dp[j]=max(dp[j],dp[j-1]-abs(diff[i]+diff[i+1])+abs(diff[i])+abs(diff[i+1]));//找一个最大的优化值
//            cout<<abs(diff[i]+diff[i+1])<<" "<<abs(diff[i])<<" "<<abs(diff[i+1])<<"               ";
//            cout<<dp[j]<<" "<<i<<" "<<j<<endl;
        }
	}
	for(int i=1;i<=n;i++){
        ans=max(dp[i],ans);
	}
	cout<<ansc-ans<<endl;
}