#include <bits/stdc++.h>
#define ll long long

using namespace std;

int n, g;
vector<vector<int>> dp;
vector<pair<int, int>> a;

int main() {
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> g;
    dp.resize(n+1, vector<int>(g+1, 0));
    a.resize(n);
    
    for(auto& it : a)
        cin >> it.first >> it.second;
        
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=g; ++j){
            if(j >= a[i-1].first)
                dp[i][j] = max(a[i-1].second + dp[i-1][j-a[i-1].first], dp[i-1][j]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    
    cout << dp[n][g];
    
    return 0;
}