#include <iostream>
#include <fstream>

using namespace std;

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

int n, GMax;
int c[5001], g[5001];
int CMax[10001], Uz[10001][5001];

void Citire()
{
    in >> n >> GMax;
    for(int i=1; i<=n; i++)
        in >> g[i] >> c[i];
    for(int i=1; i<=GMax; i++) CMax[i]=-1;
}

void Rezolvare()
{
    for(int S=1; S<=GMax; S++)
        for(int i=1; i<=n; i++)
            if(g[i]<=S && CMax[S-g[i]]!=-1 && !Uz[S-g[i]][i])
                if(CMax[S]<c[i]+CMax[S-g[i]])
                {
                    CMax[S]=c[i]+CMax[S-g[i]];
                    for(int k=1; k<=n; k++)
                        Uz[S][k]=Uz[S-g[i]][k];
                    Uz[S][i]=1;
                }
}

int main()
{
    Citire();
    Rezolvare();
    out << CMax[GMax];
    return 0;
}