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


}