#include <stdio.h>
int G,  N, W[1000],  P[1000];
int vec[1000];
int max(int a,int b)
{
    if(a>b)
    return a;
    return b;
}
int rucs()
{
    int i,j;
    for (i=1;i<=N;i++) 
    {
        for (j=G;j>= 0;j--) 
        {
            if (W[i-1]<=G)
                vec[j]=max(vec[j],vec[j-W[i-1]]+P[i-1]);
        }
    }
    return vec[G];
}
int main()
{
   FILE *in;
   FILE *out;
    in=fopen("rucsac.in","r");
    fscanf(in,"%d",&N);
    fscanf(in,"%d",&G);
    int i;
    for(i=1;i<=N;i++)
    {fscanf(in,"%d",&W[i]);
    fscanf(in,"%d",&P[i]);}
    out=fopen("rucsac.out","w");
    fprintf(out,"%d",rucs());
    return 0;
}