#include <fstream>
#define DMAX 5006
#define NMAX 10005
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,GMAX;
int cmax[NMAX],c[DMAX],g[DMAX];
void citire();
void pd();
int main(){citire();
pd();  fout<<cmax[GMAX]<<'\n';return 0;}
void citire(){int i;
fin>>n>>GMAX;
 for(i=1;i<=n;i++)fin>>g[i]>>c[i];}
void pd()
{int i,x;
for(i=1;i<=n;i++)for(x=GMAX;x>=1;x--)if(x>=g[i])if(cmax[x]<c[i]+cmax[x-g[i]])cmax[x]=c[i]+cmax[x-g[i]];}