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

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

int dp[1001][5001];
int eg[1001], cg[1001];

int main()
{
	int n, i, j, w;
	fin >> n >> w;
	for (i = 1; i<=n; i++)
		fin >> eg[i] >> cg[i];
	for (i = 0; i<=n; i++)
		for (j = 0; j<=w; j++)
			dp[i][j] = 1<<30;
	dp[0][0] = 0;
	for (i = 1; i<=n; i++)
		for (j = 0; j<w; j++)
			dp[i][j] = min (dp[i-1][j], dp[i-1][j-eg[i]] + cg[i]);
	int rasp = 1<<30;
	for (i = 1; i<=n; i++)
		for (j = w-eg[i]; j<w; j++)
			rasp = min (rasp, dp[i-1][j] + cg[i]);
	fout << rasp;
	return 0;
}