#include<fstream>
#include<vector>

using namespace std;

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

int main()
{
	vector<int> p,g,u,d;
	int n,m,i,j;
	in>>n>>m;
	p.resize(n+1);
	g.resize(n+1);
	u.resize(m+1);
	d.resize(m+1);
	for(i=1;i<=n;i++) in>>g.at(i)>>p.at(i);
	for(i=0;i<=m;i++) u.at(i)=p.at(1)*(g.at(1)<=i);
	for(j=2;j<=n;j++)
	{
		for(i=1;i<=m;i++) 
			if(i>=g.at(j)) d.at(i)=u.at(i)*(u.at(i)>=u.at(i-g.at(j))+p.at(j))+(u.at(i-g.at(j))+p.at(j))*(u.at(i)<u.at(i-g.at(j))+p.at(j));
			else d.at(i)=u.at(i);
		u=d;
	}
	out<<d.at(m);
}