#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[MAX][GMAX];

int main()
{
    cin >> n >> g;
    for(int i = 0; i < n; ++i)
    {
        cin >> w[i] >> p[i];
    }
    dp[0][0] = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j <= g; ++j)
        {
            if(j + w[i] <= g)
            {
                dp[i + 1][j + w[i]] = max(dp[i][j] + p[i], dp[i + 1][j + w[i]]);
            }
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
        }
    }
    int maxim = 0;
    for(int j = 0; j <= g; ++j)
    {
        maxim = max(maxim, dp[n][j]);
    }
    cout << maxim << '\n';
    return 0;
}