/*
    Keep It Simple!
*/

#include<fstream>

using namespace std;

#define MaxN 5005
#define MaxG 10005

int R[MaxG];
int N,G;
int W[MaxN],P[MaxN];

int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

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

    for(int i=1;i<=N;i++)
    {
        for(int j=G; j >= W[i]; j--)
        {
            R[j] = max(R[j],R[j-W[i]]+P[i]);
            if(R[j] > Max)
                Max = R[j];
        }
    }

    g << Max;
}