#include <iostream>
#include <algorithm>
#include <fstream>
#include <utility>
using namespace std;
ofstream fout("rucsac.out");
ifstream fin("rucsac.in");
int greutati[5001];
int valori[5001];
int matrice[5001][5001];

int main(){
  int n, g;
  fin>>n>>g;
  
  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;
}