#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 n,G;
int w[5010],p[5010];
int d[2][10010];

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

    int l=0;

    for(i=1; i<=n; ++i, l=1-l)
        for(j=0; j<=G; ++j)
        {
            d[1-l][j]=d[l][j];
            if(w[i]<=j)
                d[1-l][j]=maxim(d[1-l][j],d[l][j-w[i]]+p[i]);
        }
    g<<d[l][G];
    return 0;
}