#include <fstream>
#include <cstring>

const int NMAX = 5000;
const int GMAX = 10000;

int d[1+NMAX][1+GMAX];
int w[1+NMAX], p[1+NMAX];

using namespace std;

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

    int n,g;
    in>>n>>g;
    for(int i=1;i<=n;i++)
    {
        in>>w[i]>>p[i];
    }

    for(int i=1;i<=n;i++)
    {
        memcpy(d[i],d[i-1],w[i]*4);

        for(int j=w[i];j<=g;j++)
        {
            d[i][j]=max(d[i-1][j],d[i-1][j-w[i]]+p[i]);
        }
    }

    out<<d[n][g];

    return 0;
}