#include <iostream>
#include <cstdio>
using namespace std;

int r[100][100],g[100],v[100];

void rez(int G,int n)
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=G; j++)
        {
           if(r[2][j] &&r[1][j] && r[1][j]+g[i]<=G && r[2][r[1][j]+g[i]]==0)
           {
               r[2][r[1][j]+g[i]]=v[i]+r[2][j];
               int k=3;
                r[k][j+g[i]]=i;
                 r[1][r[1][j]+g[i]]=0;
           }
        }
        for(int j=1; j<=G; j++)
        {
            if(r[1][j]==g[i] && r[2][j]<v[i])
            {
                r[2][j]=v[i];
                int k=3;
                r[3][j]=i;
            }
            else if(r[2][j] && r[1][j] && r[1][r[1][j]+g[i]] && r[1][j]+g[i]<=G && r[2][r[1][j]+g[i]]<v[i]+r[2][j])
            {
                r[2][r[1][j]+g[i]]=v[i]+r[2][j];
                int k=3;
                r[k][j+g[i]]=i;
                r[1][r[1][j]+g[i]]=0;
            }

        }
        for(int l=1; l<=G; l++)
        r[1][l]=l;
    }
}

int main()
{
    FILE *f=fopen("rucsac.in","r");
    int G,n,max=0,poz;
    fscanf(f,"%d%d",&n,&G);
    for(int i=1; i<=n; i++)
        fscanf(f,"%d %d",&g[i],&v[i]);
    for(int i=1; i<=G; i++)
        r[1][i]=i;
    rez(G,n);
    f=fopen("rucsac.out","w");
    for(int i=1; i<=G; i++)
    {
       if(r[2][i]>max)
           max=r[2][i];
    }
    fprintf(f,"%d",max);
    return 0;
}