#include<fstream>

#define GMAX 1001
#define inf 2000000000

using namespace std;

int energy[GMAX];
int cost[GMAX];
int dp[2][5001];

int main()
{
	int g, w;
	int i, j;
	int l;
	int biggerC=inf;
	ifstream f("energii.in");

	f>>g>>w;
	for(i=1; i<=g; i++)
		f>>energy[i]>>cost[i];
	f.close();

	dp[0][0]=1;
	l=0;
	for(i=1; i<=g; i++)
	{
		l=1-l;
		for(j=0; j<energy[i]; j++)
			dp[i][j]=dp[i-1][j];
		for(j=energy[i]; j<=w; j++)
		{
			dp[l][j]=dp[1-l][j];
			if(dp[1-l][j-energy[i]])
			{
				if((dp[1-l][j-energy[i]]+cost[i])<dp[l][j] || dp[l][j]==0)
					dp[l][j]=dp[1-l][j-energy[i]]+cost[i];
			}
		}
		for(j=1; j<=energy[i]; j++)
			if(dp[1-l][w+j-energy[i]] && (dp[1-l][w+j-energy[i]]+cost[i]<biggerC))
				biggerC=dp[1-l][w+j-energy[i]]+cost[i];
	}
	if(dp[l][w] && dp[l][w]<biggerC)
		biggerC=dp[l][w];
	if(biggerC==inf)
		biggerC=0;
	biggerC--;
	ofstream gg("energii.out");
	gg<<biggerC<<'\n';
	gg.close();
	return 0;
}