#include <fstream>
#include <iostream>

using namespace std;

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

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

int dp[NMAX+1][GMAX+1];
int p[NMAX+1], g[NMAX+1];

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

    return 0;
}