#include<fstream>
 
using namespace std;

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

int D[2][10010],G[5010],P[5010];
int Gr,N,Maxi;
bool u;

int main(){ 
    fin>> N >> Gr;
    for(int i=1; i<=N; i++){
        fin>>G[i]>> P[i];
    }
    for (int i=1; i<=N;i++){
      for (int j=0; j<=Gr;j++){
      	D[u][j]=D[!u][j];
        if (j>=G[i]){
            D[u][j]=max(D[u][j], D[!u][j-G[i]]+P[i]);
        }
      }
      u=!u;
	}
	u=!u;
    fout << D[u][Gr];
    return 0;
}