#include<bits/stdc++.h>
using namespace std;
int h[60],ans=0,ff[60],n,m,sum[60];
int f[60][60][2];
int min(int a,int b){
	return a<b?a:b;
}
int main(){
	cin>>n>>m;
	memset(ff,270,sizeof(ff));
	for(int i=1;i<=n;i++){
		cin>>h[i]>>ff[i];
		sum[i]=sum[i-1]+ff[i];
	}
	f[m][m][0]=f[m][m][1]=0;
	for(int len=2;len<=n;len++){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			f[i][j][0]=min(f[i+1][j][0]+(sum[i]+sum[n]-sum[j])*(h[i+1]-h[i]),
			            f[i+1][j][1]+(sum[i]+sum[n]-sum[j])*(h[j]-h[i]));
			f[i][j][1]=min(f[i][j-1][0]+(sum[i-1]+sum[n]-sum[j-1])*(h[j]-h[i]),
			            f[i][j-1][1]+(sum[i-1]+sum[n]-sum[j-1])*(h[j]-h[j-1]));
		}
	}
	cout<<min(f[1][n][0],f[1][n][1])<<endl;
	return 0;
}