#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, g, dp[4][10005];
pair<int, int> v[5005];

int main()
{
    fin >> n >> g;
    for(int i=1; i<=n; i++) {
        fin >> v[i].first >> v[i].second;
    }
    dp[0][0]=0;
    int q=1;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=g; j++) {
            dp[q][j]=dp[1-q][j];
            if(j-v[i].first>=0) {
                dp[q][j]=max(dp[q][j], dp[1-q][j-v[i].first]+v[i].second);
            }
        }
        q=1-q;
    }
    fout << dp[1-q][g];
    return 0;
}