#include <fstream>
using namespace std;

#define NMAX 1002
#define SMAX 5002

#define INF 0x3FFFFFFF

const char infile[] = "energii.in";
const char outfile[] = "energii.out";


int M[SMAX];

int Energy[NMAX];
int Cost[NMAX];

int N;
int S;

int Minimum;

void Solve() 
{
	for(int i = 1 ; i < SMAX; ++i)
	{
		M[i] = INF;
	}

	for(int i = 0 ; i < N; i++)
	{
		for(int j = S; j >= 0; --j)
		{
			if(j - Energy[i] >= 0 )
			{
				M[j] = min(M[j - Energy[i]] + Cost[i], M[j]);
			}
			else if( j + Energy[i] > S && M[j] != INF)
			{
				M[S] = min( M[j] + Cost[i]  , M[S]);
			}

		}
	}
	Minimum = M[S];
}

int main(int argc, char* argv[])
{
	fstream fin(infile, ios::in);
	
	fin >> N;
	fin >> S;

	for(int i = 0 ; i < N; ++i)
	{
		fin >> Energy[i] >> Cost[i];
	}

	fin.close();


	Solve();


	fstream fout(outfile, ios::out);

	fout << Minimum << "\n";

	fout.close();

}