#include <bits/stdc++.h>



using namespace std;
int main(void){
    // Your code here!
    int N,D;
    cin>>N>>D;
    vector<int>P(N);
    vector<int>Q(N);
    
    long long dp[100010][N];


    
    for(int i=0;i<N;i++){
        cin>>P.at(i)>>Q.at(i);
    }
    
    
    int temp_min=0-P[0];
    int temp_num;
    
    for(int i=0;i<N;i++){
        if(temp_min<0-P[i]){
            temp_min=0-P[i];
            temp_num=i;
        }
    }
    
    dp[0][temp_num]=temp_min;
    
    
    for(int i=0;i<D;i++){
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k< N; ++k) {
                if (j == k) continue;
                
                dp[i+1][k]=min(dp[i+1][k],dp[i][j]+Q[j]-P[k]);
                
                
                // dp[i][j]-P[k]
                
                // dp[i+1][k]=
                
                
                // dp[i+1][k]=min(dp[i+1][k],min(dp[i][j]-P[k],dp[i][j]-P[k]+Q[k]));
                
                // dp[i+1][k]=min(dp[i+1][k],min(dp[i][j]-P[k],dp[i][j]-P[k]+Q[k]));
                // cerr<<"dp:"<<i<<" "<<dp[i+1][k]<<endl; 
             }
        }
    }
    long long ans=100000;
    
    for(int i=0;i<N;i++){
        ans=min(ans,dp[N-1][i]);
    }
    cout<<ans<<endl;
    
}