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

int mat[5003][10003];

int main(){
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
  int n, kg;
  fin>>n>>kg;
  int weight[5002], val[5002];
  for (int i=1; i<=n; ++i)
    fin>>weight[i]>>val[i];

  for(int i=1; i<=n; i++){
    for(int w=1; w<=kg; w++){
      mat[i][w]=max(mat[i-1][w], mat[i][w-1]);
      if(w >= weight[i])
      	mat[i][w]=max(val[i]+mat[i-1][w-weight[i]], mat[i][w]);
    }
  }
  fout<<mat[n][kg];
}