#include <iostream>
#include <cstdio>
using namespace std;
int g[5010],co[5010],r[5010];
int n,G;
void citire( )
{
    FILE *f=fopen("rucsac.in","r");
    fscanf(f,"%d%d",&n,&G);
    for(int i=1;i<=n;i++)
        fscanf(f,"%d%d",&g[i],&co[i]);

}
void rez( )
{
    for(int i=1;i<=n;i++)
        for(int j=G;j>=0;j--)
          if(g[i]<=j)
            r[j]=max(co[i]+r[j-g[i]],r[j]);
        FILE *f1=fopen("rucsac.out","w");
    fprintf(f1,"%d",r[G]);
}
int main()
{
    citire();
    rez();
    return 0;
}