#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e3;
const int GMAX = 1e4;

long long G[NMAX+1], P[NMAX+1];

int main()
{
    int n, w;
    f >> n >> w;
    
    long long dp[3][w+1];
    
    for(int i=1; i<=n; i++){
        f >> G[i] >> P[i];
    }
    
    for(int i=0; i<=2; i++)
        fill(dp[i], dp[i]+w+1, 0);
    
    for(int i=1; i<=n; i++){
        for(int j=0; j<=w; j++){
            
            dp[2][j] = dp[1][j];
            if(j >= G[i])
                dp[2][j] = max(dp[2][j], dp[1][j - G[i]] + P[i]);
            
        }
        for(int j=0; j<=w; j++)
            dp[1][j] = dp[2][j];
    }
    
    g << dp[1][w];
    

    return 0;
}