#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int main(){
   int n,wmax;
   fin>>n>>wmax;
   int v[n+1],w[n+1];
   for (int i=1; i<=n; ++i)
		fin>>w[i]>>v[i];
   //init matrice
   int m[5002][10002];
   for (int i=0; i<=n; ++i)
		m[i][0]=0;
	for (int i=0; i<=wmax; ++i)
		m[0][i]=0;
   //algoritm
   for (int i=1; i<=n; ++i) //itemul i
		for (int j=1; j<=wmax; ++j){ //weightul maxim
         if (w[i]>j)
				m[i][j]=m[i-1][j];
			else m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
		}
	fout<<m[n][wmax];
}