include<bits/stdc++.h>

using namespace std;

struct book {

int height , wide;

}a[200]; int f[200][200];

bool cmp(const book &a , const book &b) {

return a.height < b.height;

}

int main() {

int n , k ;
cin >> n >> k ;
for(int i=1;i<=n;i++)
    cin >> a[i].height >> a[i].wide;
sort(a+1,a+n+1 , cmp);
for(int i=1;i<=n;++i)
    for(int j=2;j<min(i,n-k);++j)
    {
        f[i][j] = 0x3f3f3f3f;
        for(int x=j-1;x<i;++x)
            f[i][j] =min(f[i][j],f[x][j-1]+abs(a[x].wide-a[i].wide));
    }
int ans = f[n][n-k];
for(int i=n-1;i>=n-k;--i)
    ans = min(ans,f[i][n-k]);
cout << ans << endl;
return 0;

}