#include <fstream>
 
using namespace std;
 
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++)
		matrice[i][0]=0;
	for (j=0; j<=n; j++)
		matrice[0][j]=0;
	for (i=0; i<=n; i++)
		for (j=0; j<=m; j++)
		{
			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;
}