#pragma GCC optimize ("O1")
#include <bits/stdc++.h>

using namespace std;

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

struct STR{
    int g,p;
}v[5000];
int dp[2][10005];

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    int n,G;
    fin >> n >> G;
    for (int i=1;i<=n;++i){
        fin >> v[i].g >> v[i].p;
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=G;++j){
            dp[1][j] = dp[0][j];
            if (j>=v[i].g) dp[1][j] = max(dp[1][j],dp[0][j-v[i].g]+v[i].p);
        }
        for (int j=1;j<=G;++j) dp[0][j] = dp[1][j];
    }
    fout << dp[0][G];
    return 0;
}