#include <fstream>

using namespace std;

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

const int DM = 5e3 + 1;

int n,G;
int dp[3][DM * 2];
pair < int, int > wp[DM];

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