#include <stdio.h>
#define nmax 1005
#define wmax 5005
#define infinit 1000000000

int N, W;

int E[nmax], C[nmax], S[nmax], CMIN[nmax][wmax];

void read()
{
	int i;

	freopen("energii.in", "r", stdin);

	scanf("%d%d", &N, &W);

	for (i = 1; i <= N; ++i)
		scanf("%d%d", &E[i], &C[i]);
}

void solve()
{
	int i, w;

	for (i = 1; i <= N; ++i)
		S[i] = S[i-1] + E[i];

	for (w = 1; w <= W; ++w)
		CMIN[0][w] = infinit;

	for (i = 1; i <= N; ++i)
	{
		for (w = 1; w <= W && w <= S[i]; ++w)
		{
			CMIN[i][w] = infinit;

			if (CMIN[i-1][w] < CMIN[i][w])
				CMIN[i][w] = CMIN[i-1][w];

			if (E[i] >= w)
			{
				if (CMIN[i][w] > C[i])
					CMIN[i][w] = C[i];
			}

			if (E[i] <= w)
			{
				if (CMIN[i][w] > C[i] + CMIN[i-1][w-E[i]])
					CMIN[i][w] = C[i] + CMIN[i-1][w-E[i]];
			}
		}
		for (w = S[i]+1; w <= W; ++w)
			CMIN[i][w] = infinit;
	}
}

void write()
{
	freopen("energii.out", "w", stdout);

	printf("%d\n", CMIN[N][W]);
}

int main()
{
	read();

	solve();

	write();

	return 0;
}