#include <iostream>
#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream m("rucsac.out");
int n,g,w,p,v[5100][10010],i,j;
int main()
{
f>>n>>g;
for(i=0;i<=n;i++)
    v[i][0]=0;
for(i=0;i<=g;i++)
    v[0][i]=0;

for(i=1;i<=n;i++)
{
    f>>w>>p;
    for(j=1;j<=g;j++)
    {
        v[i][j]=v[i-1][j];
        if(j>=w)
        v[i][j]=max(v[i][j],v[i-1][j-w]+p);
    }
}
m<<v[n][g];


    return 0;
}