#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[GMAX];
/* ----- Data ------- */

void Read_Input()
{
    scanf("%d%d",&n,&g);
    for(int i = 1; i<= n; ++i)
    {
        scanf("%d%d",&weight[i],&value[i]);
    }
    return;
}
void Construct_Solution()
{
    for(int i =1 ; i <= n; i++)
    {
        for(int k = g; k>= 0 ; k--)
        {
            if(k + weight[i] <= g)
            {
                dp[k+weight[i]] = std::max(dp[k+weight[i]], dp[k] + value[i]);
            }
        }
    }
    return;
}
void Print_Result()
{
    int sol = -1;
    for(int i = 1; i<= g; i++)
        sol = std::max(sol,dp[i]);
    printf("%d",sol);
    return;
}
int main()
{
    Read_Input();
    Construct_Solution();
    Print_Result();
    return 0;
}