#include <fstream>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n, gr, g[5005], p[5005], i, j, sol;
int c[10005];

int main() {
    cin >> n >> gr;

    for (i = 1; i <= n; ++i)
        cin >> g[i] >> p[i];

    for (i = 1; i <= n; ++i) {
        for( int j = gr - g[i]; j >= 0; --j) {
			if( c[j+g[i]] < c[j] + p[i] )
			{
				c[j+g[i]] = c[j] + p[i];
				if( c[j+g[i]] > sol)
					sol = c[j+g[i]];
			}
        }
    }

    cout << sol << "\n";

    return 0;
}