#include <fstream.h>

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

int n, g, x[10001], y[10001];
int matrice[5001][10001];

void construct_matrice(int n, int m)
{
	int i, j;
	for (i=0; i<=n; i++)
		for (j=0; j<=m; j++)
		{
			if (i==0 || j==0)
				matrice[i][j]=0;
			else
				if (j>=x[i])
				{
					if (matrice[i-1][j]>y[i]+matrice[i-1][j-x[i]])
						matrice[i][j]=matrice[i-1][j];
					else
						matrice[i][j]=y[i]+matrice[i-1][j-x[i]];
				}
				else
					matrice[i][j]=0;
		}
	i++;
}

int main()
{
	int i;
	fin>>n>>g;
	for (i=1; i<=n; i++)
		fin>>x[i]>>y[i];
	construct_matrice(n, g);
	fout<<matrice[n][g];
	fin.close();
	fout.close();
	return 0;
}