//============================================================================
// Name        : ruksak.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <fstream>
using namespace std;

int main() {
	int n,g;
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	fin>>n>>g;
	int greu[3][10001],rucv[5001],rucg[5001];
	for(int i=1;i<=n;i++)
	{
		fin>>rucg[i]>>rucv[i];
	}
	for(int i=rucg[1];i<=g;i++)
		greu[1][i]=rucv[1];
	for(int i=0;i<rucg[1];i++)
		greu[1][i]=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=rucg[i];j<=g;j++)
			if(greu[1][j]>greu[1][j-rucg[i]]+rucv[i])
			{
				greu[2][j]=greu[1][j];
			}
			else
			{
				greu[2][j]=greu[1][j-rucg[i]]+rucv[i];
			}
		for(int j=0;j<rucg[i];j++)
			greu[2][j]=greu[1][j];
		for(int j=0;j<=g;j++)
			greu[1][j]=greu[2][j];

	}
	fout<<greu[2][g];
	return 0;
}