#include <fstream>
#include <cstring>

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

int d[2][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,lin;
    in>>n>>g;
    for(int i=1;i<=n;i++)
    {
        in>>w[i]>>p[i];
    }

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

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

        lin=1-lin;
    }

    out<<d[1-lin][g];

    return 0;
}