#include<iostream>
#include<fstream>

using namespace std;

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

int maxim(int a,int b)
{
    if(a>b)
        return a;
    return b;
}

int main()
{
    int d[2][10010],i,j,n,G,w[5010],p[5010];
    f>>n>>G;
    for(i=1; i<=n; i++)
        f>>w[i]>>p[i];

    for(i=1; i<=n; i++)
        for(j=0; j<=G; j++)
            //if(w[i]>j)
            {
                d[i][j]=d[i-1][j];
            if(w[i]<=j)
                d[i][j]= maxim(d[i-1][j],d[i-1][j-w[i]]+p[i]);

            }

    g<<d[n][G];

    return 0;
}