#include <cstdio>
using namespace std;

int Gmax,n,g[5001],C[5001],vizitat[10001][5001],G,Cost[5001];

int main(){

    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    scanf("%d%d",&n,&Gmax);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&g[i],&C[i]);

         for(G=1;G<=Gmax;G++)
        for(int i=1;i<=n;i++)
            if(g[i]<=G && ! vizitat[G-g[i]][i])
                if(Cost[G] < C[i] + Cost[G-g[i]]){

                    Cost[G] = C[i] + Cost[G-g[i]];
                        for(int k=1;k<=n;k++)
                            vizitat[G][k] = vizitat[G-g[i]][k];
                            vizitat[G][i] = 1;
                }
printf("%d",Cost[Gmax]);
return 0;
}