#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[GMAX];
int W[NMAX],P[NMAX];

void rezolva()
{
    int sol = 0;
    for(int i=1; i<= N; ++i)
        for(int j=G-W[i];j>=0;--j)
        {
            if(dp[j + W[i]] < dp[j] + P[i])
            {
                dp[j+W[i]] = dp[j] + P[i];
                if(dp[j+W[i]] > sol)
                    sol = dp[j+W[i]];
            }
        }
    printf("%d",sol);
}
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();
    return 0;
}