#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int dp[2][10005];
int w[5005];
int v[5005];
int main() {
	int n, G;
	in >> n >> G;
	for(int i = 1; i <= n; i++)
	{
        in >> w[i] >> v[i];
	}
	for(int i = 1; i <= n; i++)
	{
		for(int g = 0; g <= G; g++)
		{
		    int lin = i % 2;
		    int ant = 1 - lin;
			dp[lin][g] = dp[ant][g]; /// daca nu iau obiectul i
			if(w[i] <= g)
				dp[lin][g] = max(dp[lin][g], dp[ant][g - w[i]] + v[i]);
		}
	}
	int rez = 0;
	for(int i = 0; i <= G; i++)
		rez = max(rez, dp[n % 2][i]);
	out << rez << "\n";
	return 0;
}

/**
#include <fstream>
using namespace std;
int v[10005];
int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n,g,a,b,maxx=0;
    cin >> n >> g;
    for(int i=1;i<=n;i++)
    {
        cin >> a >> b;
        for(int j=g;j>=a;j--)
            v[j]=max(v[j],b+v[j-a]);
    }
    for(int i=1;i<=g;i++)
        maxx=max(maxx,v[i]);
    cout << maxx;
    return 0;
}
*/