#include <cstdio>

using namespace std;
const int Nmax = 5005;
const int Gmax = 10005;

int w[Nmax],castig[Nmax],DP[Gmax];
int N,G;

void read()
{
    scanf("%d%d",&N,&G);
    for(int i = 1; i <= N; ++i)
        scanf("%d%d",&w[i],&castig[i]);
}

void solve()
{
    for(int i = 1 ;i <= N;++i)
        for(int j = G - w[i]; j >= 0; --j)
            if(DP[j] + castig[i] > DP[j+w[i]] )
                DP[j+w[i]] = DP[j] + castig[i];
    printf("%d",DP[G]);
}

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    read();
    solve();

    return 0;
}