#include <fstream>
 using namespace std;
 #define MXN 5001
 #define MXG 5001
 ifstream fin("rucsac.in");
 ofstream fout("rucsac.out");

 int D[MXN][MXG];
 int n,g;
 int w[MXN],p[MXN];

 int rucsac()
 {
 int i,j;
 for(i=0;i<n;i++)
 for(j=0;j<=g;j++)
 if(j<w[i+1])
 D[i+1][j]=D[i][j];
 else
 D[i+1][j]=max( D[i][j],
 D[i][j-w[i+1]]+p[i+1] );
 return D[n][g];
 }

 int main()
 {
 int i;
 fin>>n>>g;
 for(i=1;i<=n;i++)
 fin>>w[i]>>p[i];
 fout<<rucsac();
 fin.close();
 fout.close();
 return 0;
 }