#include <cstdio>
#include <algorithm>
FILE *fin = freopen("rucsac.in","r",stdin); FILE *fout = freopen("rucsac.out","w",stdout);

static const int NMAX = 5e3 + 5;
static const int GMAX = 1e4  +5;

/* ----- Data ------- */
int n,g;
int weight[NMAX], value[NMAX], dp[NMAX][GMAX];
/* ----- Data ------- */

void Read_Input()
{
    scanf("%d%d",&n,&g);
    for(int i = 1; i<= n; ++i)
    {
        scanf("%d%d",&weight[i],&value[i]);
    }
}
void Construct_Matrix()
{
    for(int i =1 ; i <= n; i++)
    {
        for(int j = 0; j <= g; j++)
        {
            dp[i][j] = dp[i-1][j];

            if(j >= weight[i])
                dp[i][j] = std::max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]);
        }
    }
}
void Print_Result()
{
    printf("%d",dp[n][g]);
}
int main()
{
    Read_Input();
    Construct_Matrix();
    Print_Result();
    return 0;
}