#include <fstream>

using namespace std;
int cost[10001],w[5001],p[5001],n,gr,i,j,profit;
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>n>>gr;
    for (i=1;i<=n;i++) f>>w[i]>>p[i];
    for (i=1;i<=n;i++)
       for (j=gr-w[i];j>=0;j--)
         if (cost[j+w[i]]<cost[j]+p[i])
           {  cost[j+w[i]]=cost[j]+p[i];
				if(cost[j+w[i]]>profit)
					profit=cost[j+w[i]];
           }
    g<<profit<<'\n';
    f.close();
    g.close();
    return 0;
}