#include <bits/stdc++.h>

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

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

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

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

    g<<DP[1-l][G];

}