#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream h("rucsac.out");
int gr[5001];
int cost[5001];
int v[3][5001];
int n,g,i,j,gmax,gmax11,cmax1;
void back(int d)
{
    if(d!=0)
    {back(d-gr[v[2][d]]);

    h<<v[2][d]<<' ';}
}
int main()
{

    f>>n>>g;
    for(i=1;i<=n;i++)
    f>>gr[i]>>cost[i];


    v[2][0]=1;
    gmax=0;

    for(i=1;i<=n;i++)
    {
        gmax11=gmax;

        for(j=gmax;j>=0;j--)
        if(v[2][j]!=0)
        {
           if(j+gr[i]<=g)
           {
               if(j+gr[i]>gmax11)
               gmax11=j+gr[i];

               if(v[1][j]+cost[i]>v[1][j+gr[i]])
               {
                   v[1][j+gr[i]]=v[1][j]+cost[i];
                   v[2][j+gr[i]]=1;

                   if(v[1][j]+cost[i]>cmax1)
                   cmax1=v[1][j+gr[i]];
               }

           }


        }
        gmax=gmax11;



    }
    h<<cmax1<<'\n';

    f.close();
    h.close();
    return 0;
}