#include <iostream>
#include <fstream>
#include <vector>
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 j=1; j<= G; ++j)
    {
        if(W[0] <= j)
            dp[0][j]=P[0];
    }
    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);
    cin >> N >> G;
    for(int i=0;i< N;++i)
    {
        cin>>W[i]>>P[i];
    }
    rezolva();
    cout << dp[N-1][G];
    return 0;
}