#include <cstdio>

#define max(a,b) ((a > b) ? a : b)

using namespace std;

int n,g,D[1000][1000];
int W[1000],P[1000];

void Read()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsca.out","w",stdout);
    scanf("%i %i",&n,&g);
    for(int i=1;i<=n;i++)
        scanf("%i %i",&W[i],&P[i]);
}

void Dinamic()
{
    int l=0;
    for(int i=1;i<=n;i++ , l = 1-l)
    {
        for(int cw=0;cw<=g;cw++)
        {
            D[1-l][cw]=D[l][cw];
            if(W[i] <= cw)
                D[1-l][cw]=max(D[1-l][cw],D[l][cw - W[i]] + P[i]);
        }
    }
    printf("%i",D[l][g]);
}

int main()
{
    Read();
    Dinamic();
    return 0;
}