#include<fstream>
using namespace std;

#define nmax 1002

int w[nmax],c[nmax],n,m,a[nmax][5002];

int mini(int b, int d)
{
	if(b<d) return b;
	else return d;
}




int main()
{
	ifstream f("energii.in");
	ofstream g("energii.out");
	
	f>>n>>m;
	
	for(int i=1;i<=n;i++)
		f>>w[i]>>c[i];
	
	
	int s=0,s2=0;
	for(int i=1;i<=n;i++)
	{
		s=s+w[i];
		s2=s2+c[i];
		for(int j=1;j<=m;j++)
		{
			if(i==1)
			{
				if(j<=w[i])
					a[i][j]=c[i];
				continue;
			}
			
			
			if(j<=w[i])
			{
				if(a[i-1][j]!=0)
				a[i][j]=mini(a[i-1][j],c[i]);
				else
					a[i][j]=c[i];
				continue;
			}
			
			
			if(j<=s && j>w[i])
			{
				a[i][j]=s2;
				continue;
			}
		}
	}
	
	g<<a[n][m];
}