#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

const int nmax=5e3, gmax=1e4;
int w[nmax], v[nmax], dp[2][gmax+1];

int main()
{
    int N, G;
    fin >> N >> G;
    for(int i=0; i<N; i++)
        fin >> w[i] >> v[i];
    for(int i=0; i<N; i++)
        for(int cw=0; cw<=gmax; cw++)
        {
            dp[i%2][cw]=dp[(i+1)%2][cw];
            if(w[i]<=cw)
                dp[i%2][cw]=max(dp[i%2][cw], dp[(i+1)%2][cw - w[i]] + v[i]);
        }
    fout << dp[(N+1)%2][G];
    return 0;
}