#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int G,g[5012],p[5012],P;
int a[2][100012];
int main(void)
{
	int n;
	fstream f,go;
	f.open("rucsac.in",ios::in);
	go.open("rucsac.out",ios::out);
	f>>n>>G;
	int i;
	for (i=1;i<=n;i++)
		f>>g[i]>>p[i];
	
	int gr;
	for (i=1;i<=n;i++)
	{
		if (i%2==1)
			for (gr=1;gr<=G;gr++)
				{
					a[1][gr]=a[0][gr];
					if(g[i]<gr)
						a[1][gr]=max(a[1][gr],a[0][gr-g[i]]+p[i]);
				}
		else
			for (gr=1;gr<=G;gr++)
			{
				a[0][gr]=a[1][gr];
				if(g[i]<=gr)
					a[0][gr]=max(a[0][gr],a[1][gr-g[i]]+p[i]);
			}
	}
	
	go<<a[n%2][G];
}