#include <cstdio>
#include <fstream>

using namespace std;
//Problema Rucsacului folosind programarea dinamica, link informativ https://www.youtube.com/watch?v=8LusJS5-AGo
#define NMAX 5001
#define GMAX 10001
int N,G, dp[NMAX][GMAX];
int W[NMAX],P[NMAX];

void rezolva()
{
    for(int i=1; i<= N; ++i)
        for(int j=0;j<=G;++j)
        {
            if(W[i] > j)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(P[i] + dp[i-1][j - W[i]], dp[i-1][j]);
        }
}
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&N,&G);
    for(int i=1;i<= N;++i)
    {
        scanf("%d%d",&W[i],&P[i]);
    }
    rezolva();
    printf("%d",dp[N][G]);
    return 0;
}