#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,tw,w[5001],v[5001],i;
void solve()
{
	int i,j;
	long dp[n+1][tw+1];
	for(i=1;i<=n;i++)dp[i][0]=0;
	for(i=1;i<w[1];i++)dp[1][i]=0;
	for(;i<=tw;i++)dp[1][i]=1;
	for(i=2;i<=n;i++)
	{
		for(j=1;j<w[i];j++)dp[i][j]=dp[i-1][j];
		for(;j<=tw;j++)dp[i][j]=max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);
	}
	fout<<dp[n][tw]<<endl;
}
int main()
{
    fin>>n>>tw;
    for(i=1;i<=n;i++)fin>>w[i]>>v[i];
    solve();
	return 0;
}