#include <stdio.h>
#include <iostream>

#define NMAX 5000
#define GMAX 10000
using namespace std;

int g,n,w[NMAX],p[NMAX],v[GMAX],ales,target,max1;
bool chosen[GMAX][NMAX];


void run()
{
    for (int i=1;i<=g;i++)
        {
            for (int j=1;j<=n;j++)
                if (i-w[j]>=0)
                    if (!chosen[i-w[j]][j] && v[i]<v[i-w[j]]+p[j])
                    {
                        v[i]=v[i-w[j]]+p[j];
                        target=i-w[j];
                        ales=j;
                    }

            for (int k=1;k<=n;k++)
                chosen[i][k]=chosen[target][k];

            chosen[i][ales]=true;

            if (max1<v[i])
            {
                max1=v[i];
            }

        }


}

int main()
{
   freopen("rucsac.in","r",stdin);
   freopen("rucsac.out","w",stdout);
    scanf("%d %d",&n,&g);
    for(int i=1;i<n+1;i++)
      scanf("%d %d",&w[i],&p[i]);


    run();
    printf("%d",max1);
    return 0;
}