#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int DP[5001][10001]= {0};
int W[5001],P[5001];
int N,G;

int main()
{
    f>>N>>G;
    for(int i=1; i<=N; i++) f>>W[i]>>P[i];

    for(int i=1; i<=N; i++)
    {
        for(int j=0; j<W[i]; j++) DP[i][j]=DP[i-1][j];
        for(int j=W[i]; j<=G; j++)
            DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+P[i]);
    }

    g<<DP[N][G];

}