#include<bits/stdc++.h>

using namespace std;

#define maxn 5010
#define maxg 10010

int G[maxn], V[maxn], A[2][maxg];
int i,j,n,g,p;

int main()
{
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	
	cin>>n>>g;
	for(i=1;i<=n;i++)
	  cin>>G[i]>>V[i];
	  
	for(i=1;i<=n;i++,p=!p)
	  for(j=0;j<=g;j++)
	    if (G[i]>j) A[p][j]=A[!p][j];
	    else A[p][j]=max(A[!p][j],A[!p][j-G[i]]+V[i]);
	    
	cout<<A[!p][g];
	return 0;
	
}