#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f=fopen("rucsac.in","r");
FILE *g=fopen("rucsac.out","w");
int N,G,i,j,dp[2][10005],rez,ng;
struct {int val,g;} O[5005];
int main()
{
    fscanf(f,"%d%d",&N,&G);
    for(i=1;i<=N;i++)
    {
        fscanf(f,"%d%d",&O[i].g,&O[i].val);
        for(j=0;j<=G;j++)
        {
            dp[i%2][j]=dp[(i-1)%2][j];
            if(j>=O[i].g)
                if(dp[i%2][j]<dp[(i-1)%2][j-O[i].g]+O[i].val)
                    dp[i%2][j]=dp[(i-1)%2][j-O[i].g]+O[i].val;
        }
    }
    fprintf(g,"%d",dp[N%2][G]);
    fclose(f);
    fclose(g);
    return 0;
}