#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++)
	{
		if(j%2)
		{
			for(i=1;i<=m;i++) 
			if(i>=g.at(j)) u.at(i)=d.at(i)*(d.at(i)>=d.at(i-g.at(j))+p.at(j))+(d.at(i-g.at(j))+p.at(j))*(d.at(i)<d.at(i-g.at(j))+p.at(j));
			else u.at(i)=d.at(i);
		}
		else
		{
			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);
		}
	}
	if(j%2) out<<u.at(m);
	else out<<d.at(m);
}