#include <stdio.h>
FILE *in,*out;
int N,G,Pmax,W[5000],P[5000],i,j,T[10001];
using namespace std;
int main()
{
    in=fopen("rucsac.in","rt");
    out=fopen("rucsac.out","wt");
    fscanf(in,"%d%d",&N,&G);
    for (i=1;i<=N;i++)
      fscanf(in,"%d%d",&W[i],&P[i]);
     for(i=1;i<=N;i++)
         for (j=G;j>=W[i];j--)
            if (T[j-W[i]]+P[i]>T[j])
                T[j]=T[j-W[i]]+P[i];

        fprintf(out,"%d",T[G]);
    fclose(in);
    fclose(out);
    return 0;
}