#include <fstream>
using namespace std;

const int lim=(1<<14)-1;
int v[lim+1];

ifstream in("energii.in");
ofstream out("energii.out");

int main()
{
	int i,j,a,b,n,k;
	in>>n>>k;
	for (i=1;i<=lim;i++)
		v[i]=lim;
	for (i=1;i<=n;i++)
	{
		in>>a>>b;
		for (j=lim;j>=0;j--)
			if (v[j]!=lim && v[j+a]>v[j]+b)
				v[j+a]=v[j]+b;
	}
	for (i=lim-1;i;i--)
		if (v[i]>v[i+1])
			v[i]=v[i+1];
	out<<v[k]<<"\n";
	return 0;
}