#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int i,j,n,m,G,w[5002],p[5002],v[10002];
int main()
{
    fin>>n>>G;
    for(i=1;i<=n;i++)
        fin>>w[i]>>p[i];
         for(j=w[1];j<=G;j++)
            v[j]=p[1];
        for(i=2;i<=n;i++)
            for(j=G;j>=1;j--)
        if(v[j]<p[i]+v[j-w[i]]&&j-w[i]>=0)
        v[j]=p[i]+v[j-w[i]];
        fout<<v[G];
    return 0;
}