#include <fstream>
using namespace std;
const int NMAX=5005;
int d[10005];
struct sp
{
    int w;
    int p;
} v[NMAX];
int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    int n, w, sol=0, j, i;
    in>>n>>w;
    for(i=1; i<=n; i++)
    {
        in>>v[i].w>>v[i].p;
    }
    for(i=1; i<=n; i++)
        for(j=w-v[i].w; j>=0; j--)
            if(d[v[i].w+j]<d[j]+v[i].p)
            {
                d[v[i].w+j]=d[j]+v[i].p;
                if(d[j+v[i].w]>sol)
                    sol=d[j+v[i].w];
            }
    out<<sol<<'\n';
    return 0;
}