/*
PROG: charm
LANG: C++
ID: gabitzish1
*/

#include <stdio.h>
#include <stdlib.h>

int n, w;
long charm[10000];

typedef struct
{
	int g, c;
} margea;

margea a[1000];

void citire()
{
	freopen("energii","r",stdin);
	freopen("energii.out","w",stdout);

	int i;
	scanf("%d %d", &n, &w);
	for (i = 1; i <= n; i++)
		scanf("%d %d", &a[i].g, &a[i].c);
}

int main()
{
	citire();
	int i, j, max = 0;
	
	for (i = 1; i <= n; i++)
	{
		for (j = w; j >= 1; j--)
			if (charm[j])
				if (charm[j] + a[i].c < charm[j + a[i].g] || a[j + a[i].g] == 0) charm[j + a[i].g] = charm[j] + a[i].c;
		if (charm[a[i].g] > a[i].c || charm[a[i].g] == 0) charm[a[i].g] = a[i].c;
	}
	
	for (i = 1; i <= w; i++) if (charm[i] > max) max = charm[i];
	printf("%d\n", max);
	return 0;
}