rt

#include<bits/stdc++.h>
using namespace std;
int n,k,dp[105];
struct str{
	int a;
	int c;
}s[105];
bool ps(str &x,str &y){
	return x.a>y.a;
}
void dfs(int x,int y,int z){
	if(y>=dp[z]){
		return;
	}
	dp[z]=y;
	if(z<k){
		for(int i=x+1;i<=n;i++){
		    dfs(i,y+abs(s[x].c-s[i].c),z+1);
	    }
	}
}
int main(){
	memset(dp,127,sizeof(dp));
	cin>>n>>k;
	k=n-k;
	for(int i=1;i<=n;i++){
		cin>>s[i].a>>s[i].c;
	}
	sort(s+1,s+n+1,ps);
	for(int i=1;i<=n;i++){
		dfs(i,0,1);
	}
	cout<<dp[k];
	return 0;
}