#include<fstream>
#define G first
#define P second
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,pmax[3][10005],i,j,g,ma,lc,lp;
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++)
    {
        lc=i%2;
        lp=1-lc;
        for(j=1;j<=g;j++)
            if(j-x[i].G>=0)
            {
                if(j==x[i].G||pmax[i%2-1][j-x[i].G]>0)
                    pmax[lc][j]=max(pmax[lp][j-x[i].G]+x[i].P,pmax[lp][j]);
                else
                    pmax[lc][j]=pmax[lp][j];
            }
            else
                pmax[lc][j]=pmax[lp][j];
    }
    ma=pmax[n%2][g];
    for(i=g-1;i>=1;i--)
        if(pmax[n%2][i]>ma)
            ma=pmax[n%2][i];
    fout<<ma;


}