#include <bits/stdc++.h>
using namespace std;
int n,k;
pair<int,int> books[105];
int dif[105],sum[105];	//相邻两本书的宽度之差数组以及差的前缀和数组
int dp[105][105];		//dp[i][j]表示前i本书，拿出来j本后的不整齐度 dp[i][j]=min(dp[i-1][j-1],min(dp[l-1][j-1]+abs(books[l+1].second-books[l-1].second)+(sum[i]-sum[l+1])))   (j<=l<i)
bool cmp(pair<int,int>x,pair<int,int>y){
	return x.first<y.first;
}
void init(){
	for(int i=1;i<n;i++){
		dif[i]=abs(books[i].second-books[i+1].second);
		sum[i+1]=sum[i]+dif[i];
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>books[i].first>>books[i].second;
	}
	sort(books+1,books+n+1,cmp);
	init();
	for(int i=1;i<=n;i++){
		dp[i][0]=sum[i];
		for(int j=1;j<=min(i,k);j++){
			dp[i][j]=dp[i-1][j-1];  //拿走第i本书
			for(int l=j;l<i;l++){
				dp[i][j]=min(dp[i][j],dp[l-1][j-1]+((l==1)?0:abs(books[l+1].second-books[l-1].second))+(sum[i]-sum[l+1]));
			}
		}
	}
	cout<<dp[n][k];
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<=k;j++){
//			cout<<dp[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	return 0;
}