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

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