#include <iostream>
#include <algorithm>
#include <fstream>
#include <utility>
using namespace std;
ofstream fout("rucsac.out");
ifstream fin("rucsac.in");

int main(){
  int n, g;
  fin>>n>>g;

  int greutati[n+1];
  int valori[n+1];
  int matrice[n+1][g+1];
  
  for (int i = 0; i < n; i++){
    int x,y;
    fin>>x>>y;
    greutati[i+1] = x;
    valori[i+1] = y;
  }

  for (int i = 0; i <= n; i++){
    for (int j = 0; j <= g; j++){

      if(i == 0){
        matrice[i][j] = 0;
        continue;
      }
      matrice[i][j] = 0;

      if(greutati[i] > j){
        matrice[i][j] = matrice[i-1][j];
      }else{
        matrice[i][j] = max(matrice[i-1][j], valori[i] + 
              matrice[i-1][max(0, j-greutati[i])]);
      }


    }
  }

  fout<<matrice[n][g];

  return 0;
}