#include<fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int NMAX=5005,GMAX=10005;
int G[NMAX],P[NMAX],g,n,i,j,alt;
int mat[2][GMAX];
int main()
{
    fin>>n>>g;
    for(i=1;i<=n;++i)
        fin>>G[i]>>P[i];
    for(i=1;i<=n;++i,alt=1-alt)
        for(j=0;j<=g;++j)
        {
            mat[alt][j]=mat[1-alt][j];
            if(G[i]<=j)
                mat[alt][j]=max(mat[alt][j],mat[1-alt][j-G[i]]+P[i]);
        }
    fout<<mat[1-alt][g];
}