#include<fstream>
#define G first
#define P second
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,pmax[5005][10005],i,j,g,ma;
pair<int,int >x[5005];
int main()
{
    fin>>n>>g;
    for(i=1;i<=n;i++)
    {
        fin>>x[i].G>>x[i].P;

    }
    pmax[1][x[1].G]=x[1].P;
    for(i=2;i<=n;i++)
        for(j=1;j<=g;j++)
            if(j-x[i].G>=0)
            {
                if(j==x[i].G||pmax[i-1][j-x[i].G]>0)
                    pmax[i][j]=max(pmax[i-1][j-x[i].G]+x[i].P,pmax[i-1][j]);
                else
                    pmax[i][j]=pmax[i-1][j];
            }
            else
                pmax[i][j]=pmax[i-1][j];

    ma=pmax[n][g];
    for(i=g-1;i>=1;i--)
        if(pmax[n][i]>ma)
            ma=pmax[n][i];
    fout<<ma;


}