#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;
	v[0]=1;
	for (i=1;i<=n;i++)
	{
		in>>a>>b;
		for (j=lim-a;j>=0;j--)
			if (v[j] && (v[j+a]>v[j]+b || !v[j+a]))
				v[j+a]=v[j]+b;
	}
	for (i=lim;!v[i];i--);
	for (i--;i;i--)
		if (v[i]>v[i+1] || !v[i])
			v[i]=v[i+1];
	out<<v[k]-1<<"\n";
	return 0;
}