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