#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;
	 }