#include<bits/stdc++.h>
using namespace std;
struct book
{
	int h,w;
}bk[101];
bool cmp(book x,book y)
{
	return x.h<y.h;
}
int main()
{
	int n,k,p,dp[101][101][2];
	cin>>n>>k;p=n-k;
	for(int i=1;i<=n;i++)
		cin>>bk[i].h>>bk[i].w;
	sort(bk+1,bk+n+1,cmp);
	dp[0][0][0]=-bk[1].w;
//	cout<<endl;
	for(int i=1;i<=n;i++)
	{
		dp[i][i][1]=bk[i].w;
		dp[i][i][0]=dp[i-1][i-1][0]+abs(dp[i-1][i-1][1]-dp[i][i][1]);
		dp[i][1][0]=0;dp[i][1][1]=bk[i].w;
	}
	for(int j=2;j<=p;j++)
		for(int i=j+1;i<=n;i++)
		{
			dp[i][j][0]=dp[i-1][j][0];
			dp[i][j][1]=dp[i-1][j][1];
			for(int x=j-1;x<i;x++)
				if(dp[x][j-1][0]+abs(dp[x][j-1][1]-bk[i].w)<=dp[i][j][0])
				{
					dp[i][j][0]=dp[x][j-1][0]+abs(dp[x][j-1][1]-bk[i].w);
					dp[i][j][1]=bk[i].w;
				 } 
		}
	cout<<dp[n][p][0];
//	for(int j=1;j<=p;j++)
//		for(int i=j;i<=n;i++)
//			cout<<dp[i][j][0]<<" "<<dp[i][j][1]<<endl;
}