#include <fstream>

using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

void citire();
void pd();
void afisare();

int n, w[501], c[501], gmax;
int cmax[501], uz[1001][501];

int main()
{
    citire();
    pd();
    afisare();
    return 0;
}

void citire()
{
    int i;
    fin>>n>>gmax;
    for(i=1;i<=n;i++)
        fin>>w[i]>>c[i];
}

void pd ()
{
    int g, i, j, poz, x;
    for(g=0;g<=gmax;g++)
    {
        for(i=1;i<=n;i++)
        {
            if(w[i]<=g && uz[g-w[i]][i]==0)
                x=c[i]+cmax[g-w[i]];
            else
                x=c[i];
            if(x>cmax[g])
            {
                cmax[g]=x;
                poz=i;
            }
        }
        for(j=1;j<=n;j++)
            if(j!=poz)
                uz[g][j]=uz[g-w[poz]][j];
        uz[g][poz]=1;
    }
}

void afisare()
{
    int g;
    for(g=gmax-1;g>=1;g--)
        if(cmax[g]>cmax[g-1])
        {
            fout<<cmax[g]<<'\n';
            break;
        }
}