#include<fstream>
#include<cstring>
using namespace std;

int w,ge;
int G[1002];
int E[1002];
int S[5002];

inline int Min( int a, int b ) { return ( a<b?a:b); }

int main(){
	
	ifstream f("energii.in");
	ofstream g("energii.out");
	
	f>>ge>>w;
	int i,j;
	for(i=1;i<=ge;i++) f>>G[i]>>E[i];
	
	for( i=1;i<=w;i++)S[i]=50000;
	
	for(i=1;i<=ge;i++)
		for(j=w;j>=0;j--)
			if( S[j] != 50000 ) 
			{
				if( j + E[i] < w )
				{
					if( S[j+E[i]] > S[j] + G[i] ) S[j+E[i]] = S[j]+G[i];
				}
				else
				{
					if ( S[j] + G[i] < S[w] ) S[w] = S[j] + G[i];
				}	
			}
			
			g<<S[w];
	return 0;
}