#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
using namespace std;
int f[60][60][10],n,c,d[60],p[60],pt[60][60],w[60][60],pw[60];

int main()
{
	scanf("%d%d",&n,&c);
	for(int i=1;i<=n;i++)scanf("%d%d",&d[i],&p[i]);
	for(int i=1;i<=n;i++)pw[i]=pw[i-1]+p[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			w[i][j]=w[j][i]=d[j]-d[i];
			pt[i][j]=pw[i-1]+pw[n]-pw[j];
		}
	}
	for(int i=c-1;i>=1;i--)f[i][c][0]=f[i+1][c][0]+w[i][i+1]*pt[i+1][c];
	for(int i=c+1;i<=n;i++)f[c][i][1]=f[c][i-1][1]+w[i-1][i]*pt[c][i-1];
	for(int j=c+1;j<=n;j++)
	{
		for(int i=c-1;i>=1;i--)
		{
			if(i==c-1)	f[i][j][0]=f[i+1][j][1]+w[i][j]*pt[i+1][j];
			else	f[i][j][0]=min(f[i+1][j][0]+w[i][i+1]*pt[i+1][j],f[i+1][j][1]+w[i][j]*pt[i+1][j]);
			if(j==c+1)	f[i][j][1]=f[i][j-1][0]+w[i][j]*pt[i][j-1];
			else	f[i][j][1]=min(f[i][j-1][0]+w[i][j]*pt[i][j-1],f[i][j-1][1]+w[j-1][j]*pt[i][j-1]);
		}
	}
	printf("%d",min(f[1][n][0],f[1][n][1]));
}