#include <fstream>

#define NMAX 5002
#define GMAX 10002

using namespace std;

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

int N, G;
int w[NMAX], p[NMAX];
long long int dp[GMAX];

int main()
{
    int i, j;
    fin>>N>>G;
    for(i = 1; i <= N; i++) fin>>w[i]>>p[i];
    for(i = 1; i <= N; i++) //iau fiecare obiect
        for(j = G - w[i]; j >= 0; j--)
            dp[j + w[i]] = max(dp[j] + p[i], dp[j + w[i]]);

    fout<<dp[G]<<'\n';
    return 0;
}