#include<fstream>
#include<iostream>
#define MXN 5005
#define MXG 5005
using namespace std;
ifstream fin("rucsac.in" );
ofstream fout( "rucsac.out");
int V[10005];
int n,g,k;
int w[MXN],p[MXN];
int rucsac()
{int i,j;
for (i=1;i<=n;i++)
for(j=g;j>=w[i];j--)
V[j]=max(V[j],V[j-w[i]]+p[i]);
return V[g];}
int main()
{int i;
fin>>n>>g;
for (i=1;i<=n;i++) fin>>w[i]>>p[i];
fout<<rucsac();
return 0;}