#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[n+1][w+1];
    for(int i=1; i<=n; i++){
        f >> G[i] >> P[i];
    }
    
    for(int i=0; i<=n; i++)
        fill(dp[i], dp[i]+w+1, 0);
   
    
    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])
                dp[i][j] = max(dp[i][j], dp[i-1][j - G[i]] + P[i]);
                
        }
    
    g << dp[n][w];
    

    return 0;
}