#include <iostream>
#include <queue>
#include <algorithm>
#include<set>
#include <map>
using namespace std;
using ll = long long;

int inf = 1e9;
int n, k_;

int dp[101][5005]; // dp[i][j] -> i초 일대 j만큼의 s인 상태에서 가지고 있는 당근의 수

pair<int, int> upgrades[101]; // {i, j} i만큼 지불해서 +j 만큼 더 얻을 수 있음

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k_;
    
    
    for(int i = 1; i <= n; i++){
        int a, b;
        
        cin >> a >> b;
        upgrades[i] = {a, b};
    }

    for(int i = 0; i <= k_; i++){
        for(int j = 0; j < 5005; j++) dp[i][j] = -1;
    }
    
    
    dp[0][1] = 0;
    
    for(int i = 0; i < k_; i++){
        
        for(int j = 1; j < 5005; j++){
            
            if(dp[i][j] == -1) continue;
            
            for(int k = 1; k <= n; k++){
                auto [a, b] = upgrades[k];
                
                
                if(dp[i][j] < a) continue;
                
                dp[i+1][j+b] = max(dp[i][j] - a, dp[i+1][j+b]);
            }
            
            dp[i+1][j] = max(dp[i][j] + j, dp[i+1][j]);
        }
        
    }
    
    int result = 0;
    for(int j = 1; j < 5005; j++) result = max(dp[k_][j], result);
    
    cout << result;
    
    return 0;
}