#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream gout("rucsac.out");

int n,g,w[10001],p[10001],i,j,t[10001][10001];
int main()
{f>>n>>g;
for(i=1;i<=n;i++){f>>w[i]>>p[i];}

for(i=0;i<=g;i++)
    t[0][i]=0;
for(i=1;i<=n;i++)
    for(j=0;j<=g;j++)
{
    if(w[i]>j)
        t[i][j]=t[i-1][j];
    else t[i][j]=max(t[i-1][j], t[i-1][j-w[i]]+p[i]);
}
gout<<t[n][g];
    return 0;
}