#include<fstream>
using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int W[5010],P[5010],D[10010],used[5050],best;
int n,g,i,j;

int main()
{
    cin>>n>>g;
    for (i=1;i<=n;i++) cin>>W[i]>>P[i];
    for (i=1;i<=n;i++)
        for (j=g-W[i];j>=0;j--)
          if (D[j+W[i]]<D[j]+P[i])
            D[j+W[i]]=D[j]+P[i],
            best=max(best, D[j+W[i]]);
    cout<<best;
    return  0;
}