#include <fstream>
#include <iostream>

using namespace std;

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

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

int dp[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=w; j>=0; j--){
            
            if(j - g[i] >= 0)
                dp[j] = max(dp[j], dp[j - g[i]] + p[i]);
        }
    }
   gout << dp[w];
        
    

    return 0;
}