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

static const int NMAX = 5000 + 5;
static const int GMAX = 10000+5;
/* ------- DATA ------------ */
int n, g;
int weight[NMAX], profit[NMAX], dp[GMAX];
/* ------- DATA ------------ */

void Read_Input()
{
    scanf("%d%d",&n,&g);
    for(int i =1 ;i<= n; i++)
    {
        scanf("%d%d",&weight[i],&profit[i]);
    }
}

void Solve()
{
    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] + profit[i]);
            }
        }
    }
}

int main()
{
    Read_Input();
    Solve();
    int res = -1;
    for(int i =1; i<= g; i++)
        res = std::max(res,dp[i]);
    printf("%d",res);
    return 0;
}