#include <iostream>
#include <fstream>
using namespace std;
#define MXN 5001
#define MXG 5001
ifstream fin("energii.in");
ofstream fout("energii.out");
int D[MXN][MXG];
int n,g;
int w[MXN],p[MXN];

int max(int a,int b)
 {
 if(a>b) return a;
 else return b;
 }

 int rucsac(int i,int j)
 {
 if(i==0) return 0;

 if(D[i][j]!=0) return D[i][j];
 if(j<w[i]) return D[i-1][j]=rucsac(i-1,j);
 return D[i][j]=max(rucsac(i-1,j),
 rucsac(i-1,j-w[i])+p[i]);
 }

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