#include <fstream>

#define NMAX 5005
#define GMAX 10005

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int w[NMAX], p[NMAX], dp[2][GMAX];

int main()
{
    int n, g;
    fin >> n >> g;

    for(int i = 1; i <= n; ++i)
        fin >> w[i] >> p[i];

	int lin = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= g; ++j)
        {
        	if(w[i] <= j)
				dp[lin][j] = max(dp[!lin][j], dp[!lin][j - w[i]] + p[i]);
			else {
				dp[lin][j] = dp[!lin][j];
			}
        }
        lin = !lin;
    }
	lin = !lin;

	fout << dp[lin][g] << '\n';
    return 0;
}