#include <cstdio>
#include <algorithm>

#define maxN 1005
#define maxW 5005
#define INF 0x3f3f3f3f

using namespace std;

FILE *f = fopen ("energii.in","r");
FILE *g = fopen ("energii.out","w");

int n, Ww, P[maxN], W[maxN], SOL = INF;
int D[maxN][maxW];

void read()
{
	fscanf (f, "%d%d", &n, &Ww);
	for (int i = 1; i <= n; i++)
		fscanf (f, "%d%d", &W[i], &P[i]);
}

void rucsac()
{
	for (int i = 1; i <= n; i++)
		for (int cw = 0; cw <= Ww; cw++)
		{
			D[i][cw] = D[i - 1][cw];
			
			if (W[i] <= cw)
				D[i][cw] = max(D[i][cw], D[i - 1][cw - W[i] ] + P[i]);
		}
}

void solve()
{
	for (int i = n; i >= 1; i--)
		if (D[i][Ww] < SOL && D[i][Ww] >= Ww)
			SOL = D[n][Ww];
}

int main()
{
	read();
	rucsac();
	solve();
	
	fprintf (g, "%d\n", SOL);
	
	fclose(f);
	fclose(g);
	
	return 0;
}