#include <iostream>
#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n , G , sol , l;
int w[5001] , p[5001];
int dp[2][10001];

int main()
{
    f >> n >> G;
    for(int i = 1 ; i <= n ; ++i)
        f >> w[i] >> p[i];
    for(int i = 1 ; i <= n ; ++i , l = 1 - l)
        for(int j = 0 ; j <= G ; ++j){
            dp[l][j] = dp[1 - l][j];
            if(w[i] <= j)
                dp[l][j] = max(dp[l][j] , dp[1 - l][j - w[i]] + p[i]);
            if(sol < dp[l][j])
                sol = dp[l][j];
        }
    g << sol;
    return 0;
}