using namespace std;
#include<fstream>
ifstream fin("energii.in");
ofstream fout("energii.out");
int DP[1005][5005], G, W, E[1005],C[1005];
void Read()
{
	int i;
	fin>>G>>W;
	for(i=1;i<=G;i++)
	{
		fin>>E[i]>>C[i];
	}
}
void Solve()
{
	int i,j;
	DP[1][E[1]]=C[1];
	for(i=1;i<=G;i++)
	{
		for(j=1;j<=W;j++)
		{
			if(j-E[i]<=W)
			DP[i][j]=DP[i][j-E[i]]+C[i];
			else
			DP[i][j]=min(DP[i][j],DP[i][W-E[i]]+C[i]);
		}
	}
}
void Print()
{
	fout<<DP[G][W];
}
int main()
{
	Read();
	Solve();
	Print();
	return 0;
}