#include<fstream>

#define GMAX 1001
#define inf 2000000000

using namespace std;

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

int main()
{
	int g, w;
	int i, j;
	//int l;
	int biggerW;
	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[i][j]=dp[i-1][j];
			if(dp[i-1][j-energy[i]])
			{
				//if(dp[i][j]==0 || dp[i][j]>dp[i-1][j])
				//	dp[i][j]=dp[i-1][j];
			
				if((dp[i-1][j-energy[i]]+cost[i])<dp[i][j] || dp[i][j]==0)
					dp[i][j]=dp[i-1][j-energy[i]]+cost[i];
			}
		}
		for(j=1; j<=energy[i]; j++)
			if(dp[i-1][w+j-energy[i]] && (dp[i-1][w+j-energy[i]]+cost[i]<biggerC))
			{
				biggerC=dp[i-1][w+j-energy[i]]+cost[i];
				biggerW=w+j;
			}
	}
	if(dp[g][w] && dp[g][w]<biggerC)
	{
		biggerC=dp[g][w];
		biggerW=w;
	}
	if(biggerC==inf)
		biggerC=0;
	biggerC--;
	ofstream gg("energii.out");
	gg<<biggerC<<'\n';
	gg.close();
	return 0;
}