#include <fstream>
#include <iostream>
#define INFINIT (1<<30)
//#define DEBUG true
using namespace std;

int G,W,E[1001],C[1001];
int sol[1001][5001];
//	sol[i][j] = costum minim necesar pentru a obtine j energie
//				folosind primele i generatoare
// raspunsul va fi in sol[G][W];

inline int mmin(int a,int b){
	if (a < b)
		return a;
	return b;
}

int main(){
	ifstream fin("energii.in");
	fin >> G >> W;
	for(int i = 1; i <= G ;++ i)
		fin >> E[i] >> C[i];
	fin.close();
	
	for (int j = 1 ; j<= W ; ++j)
		sol[0][j]=INFINIT; //pentru a obtine j energie cu zero generatoare
	for(int i = 1 ; i <= G ; ++i)
		sol[i][0] = 0;//pentru a obtine 0 energie cu i generatoare, costul este 0
	
	for (int i = 1; i <= G ; ++i)
		for(int j = 1 ; j <= W ; ++j)
		{
			sol[i][j] = sol[i-1][j];
			if(j-E[i] >= 0 && sol[i][j] > sol[i-1][j-E[i]]+C[i])
				sol[i][j] = sol[i-1][j-E[i]]+C[i];
		}
	
	ofstream fout("energii.out");
	fout <<sol[G][W]<<endl;
	#ifdef DEBUG
	for (int i = 0; i <= G ; ++i){
		for(int j = 0 ; j <= W ; ++j){
			if(sol[i][j]<INFINIT)
				cout << sol[i][j];
			else
				cout <<'-';
			cout<< " ";
		}
		cout << endl;
	}
	#endif
	return 0;
	
}