#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,k,f[110][110],head[110],nxt[10010],to[10010],wgh[10010],cost[10010],cnt;
struct book{
	int h,w;
	bool operator <(book b2){
		return h<b2.h;
	}
}b[110];
void add(int u,int v,int w,int c){
	to[++cnt]=v;
	wgh[cnt]=w;
	cost[cnt]=c;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
void dfs(int x,int fa,int lc,int nc,int nw){
	f[x][lc+nc]=min(f[x][lc+nc],f[fa][lc]+nw);
	for(int i=head[x];i;i=nxt[i]){
		int ti=to[i],wi=wgh[i],ci=cost[i];
		if(ti==fa || ti>=n+2)
			continue;
		dfs(ti,x,lc+nc,ci,wi);
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&b[i].h,&b[i].w);
	sort(b+1,b+n+1);
	for(int i=0;i<=n;i++)
		for(int j=i+1;j<=min(n+1,i+k+1);j++){
			int w=(!i || j==n+1)?0:abs(b[i].w-b[j].w);
			add(i,j,w,j-i-1);
		}
	memset(f,0x3f,sizeof(f));
	dfs(0,-1,0,0,0);
	printf("%d",f[n][k]);
	return 0;
}