#include <bits/stdc++.h> using namespace std; long long ans,n,k,f[1097][1097]; struct book { long long high,wide; }a[100097]; bool cmp(book x,book y) { return x.high<y.high; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].high>>a[i].wide; } sort(a+1,a+1+n,cmp); for(long long 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].high)); } } } ans=f[n][n-k]; for(long long i=n-1;i>=n-k;i--) { ans=min(ans,f[i][n-k]); } cout<<ans; return 0; }