#include <cstdio>

const int INF = 9999999;
int C[1001][1001], EG[1001], CG[1001];
int main()
{
	FILE *f = fopen("energii.in", "r");
	FILE *g = fopen("energii.out", "w");
	
	int n, W;
	
	fscanf(f, "%d %d", &n, &W);
	
	for (int i = 1 ; i <= n ; ++i)
	{
		fscanf(f, "%d %d", &EG[i], &CG[i]);
	}
	
	for (int i = 1 ; i <= W ; ++i)
		C[0][i] = INF;
	
	for (int i = 1; i <= n ; ++i)
	{
		for (int j = 1 ; j <= W ; ++j)
		{
			C[i][j] = C[i - 1][j];
			if (j - EG[i] <= 0)
			{
				if (CG[i] < C[i][j])
					C[i][j] = CG[i];
			}
			else if (C[i - 1][j - EG[i]] + CG[i] < C[i][j])
				C[i][j] = C[i - 1][j - EG[i]] + CG[i];
		}
	}
	
	fprintf(g,"%d\n",C[n][W]);
	
	return 0;
}