#include <iostream>
#include <fstream>
#define INFINIT 1000000000
using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

int w[5005],p[5005],n,puterenecesara, a[5005][500];

int main(){
	fin >> n >> puterenecesara;
	for(int i=1;i<=n;i++)
		fin >> w[i] >> p[i];
	
	for(int j = 1 ; j <=  puterenecesara ; j ++)
		a[0][j] = INFINIT;
	
	for(int i=1 ; i<=n ; i++)
			for(int j = 1 ; j <= puterenecesara ; j ++)
			{
				a[i][j] =a[i-1][j]; // costul obtinerii a j energie cu primele i-1 generatoare
				if(w[i] >= j)
					if(p[i] < a[i][j])
						a[i][j] = p[i];
				if(w[i] <= j)
					if(a[i][j] > a[i-1][j-w[i]] + p[i])
						a[i][j] = a[i-1][j-w[i]] + p[i];
			}
	fout << a[n][puterenecesara];
	
	
	
	
	return 0;
}