#include <fstream>
using namespace std;
 
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
 
#define MAX 5005
#define GMAX 10005
 
int n, g, w[MAX], p[MAX], dp[2][GMAX];
 
int main()
{
    cin >> n >> g;
    for(int i = 0; i < n; ++i)
    {
        cin >> w[i] >> p[i];
    }
    int k = 0;
    dp[0][0] = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < GMAX; ++j)
        {
            dp[1 - k][j] = 0;
        }
        for(int j = 0; j <= g; ++j)
        {
            if(j + w[i] <= g)
            {
                dp[1 - k][j + w[i]] = max(dp[k][j] + p[i], dp[1 - k][j + w[i]]);
            }
            dp[1 - k][j] = max(dp[k][j], dp[1 - k][j]);
        }
        k = 1 - k;
    }
    int maxim = 0;
    for(int j = 0; j <= g; ++j)
    {
        maxim = max(maxim, dp[k][j]);
    }
    cout << maxim << '\n';
    return 0;
}