// Rucsac.cpp : Defines the entry point for the console application.
//

#include<fstream>
#include<iostream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int a[100][3], n, G, rez[1000][1000],i,j;

int main()
{
	
	f >> n >> G;
	
	for (i = 1; i <= n; i++)
		f >> a[i][0] >> a[i][1];

	for (i = 1; i <= n; i++)
		for (j = 1; j <= G; j++)
				if ((j >= a[i][0]) && (rez[i - 1][j] < a[i][1] + rez[i - 1][j - a[i][0]]))
					rez[i][j] = a[i][1] + rez[i - 1][j - a[i][0]];
				else
					rez[i][j] = rez[i - 1][j];

	g << rez[n][G];
	f.close();
	g.close();
    return 0;
}