#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct segment_tree_1
{
    int l,r,mid,x;
}st[2*64+2];

int n,m;
int a[50+1];
int p[50+1];
int f[50+1][50+1][1+1];

void build_segment_tree_1(int now,int l,int r)
{
    st[now].l=l,st[now].r=r,st[now].mid=(l+r)/2;
    if (l<r)
    {
        if (l<=st[now].mid)
            build_segment_tree_1(now*2,l,st[now].mid);
        if (st[now].mid+1<=r)
            build_segment_tree_1(now*2+1,st[now].mid+1,r);
    }
    if (l==r)
        st[now].x=p[l];
    else
        st[now].x=st[now*2].x+st[now*2+1].x;
}

int sum_1(int now,int l,int r)
{
    if (l>r)
        return 0;
    else if (st[now].l==l&&r==st[now].r)
        return st[now].x;
    else if (r<=st[now].mid)
        return sum_1(now*2,l,r);
    else if (st[now].mid+1<=l)
        return sum_1(now*2+1,l,r);
    else
        return sum_1(now*2,l,st[now].mid)+sum_1(now*2+1,st[now].mid+1,r);
}

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        for (int i=1;i<=n;i++)
            scanf("%d%d",&a[i],&p[i]);
        build_segment_tree_1(1,1,n);
        memset(f,oo_max,sizeof(f));
        f[m][m][0]=f[m][m][1]=0;
        for (int l=1;l<=n;l++)
            for (int i=1;i<=n-l+1;i++)
            {
                int j=i+l-1;
                f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[i+1]-a[i]));
                f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[j]-a[i]));
                f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[i]));
                f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[j-1]));
            }
        printf("%d\n",min(f[1][n][0],f[1][n][1]));
    }
}