#include <stdio.h>
#define MAXN 40000
#define MAXG 1024

int best[MAXN],c[MAXG],e[MAXG];
bool viz[MAXN];

int main()
{
	freopen("energii.in","r",stdin);
	freopen("energii.out","w",stdout);

	int nrg,cmin,i,j,min = 99999999;
	scanf("%d%d",&nrg,&cmin);
	for (i=1;i<=nrg;i++)
	{
		scanf("%d%d",&c[i],&e[i]);
	}

	best[0] = 0;
	for (i=1;i<=nrg;i++)
	{
		if (best[c[i]]<e[i])
		{
			best[c[i]] = e[i];
			viz[c[i]] = true;
			if (best[c[i]]>=cmin)
			{
				if (c[i]<min)
				{
					min = c[i];
				}
			}
		}
		for (j=1;j<=cmin;j++)
		{
			if (viz[j])
			{
				viz[j] = false;
			}
			else if (best[j] != 0)
			{
				if (best[j+c[i]] < best[j]+e[i])
				{
					best[j+c[i]] = best[j] + e[i];
					viz[j+c[i]] = true;
				}
				if (best[j] + e[i]>=cmin)
				{
					if (j+c[i]<min)
					{
						min = j+c[i];
					}
					break;
				}
			}
		}
	}
	printf("%d",best[min]);
	return 0;
}