#include <fstream>
using namespace std;
int d[3][10001], masa[5001], val[5001], nr=0;
int main(){
  ifstream fin("rucsac.in");
  ofstream fout("rucsac.out");
    int n, G, maxg=-1;
    fin>>n>>G;
    for(int i=1; i<=n; i++)
      fin>>masa[i]>>val[i];
    for(int i=1; i<=n;i++){
      for(int g=0;g<=G;g++)
        if(g>=masa[i])
          d[i%2][g]=max(d[1-i%2][g-masa[i]]+val[i], d[1-i%2][g]);
        else
          d[i%2][g]=d[1-i%2][g];
    }
    fout<<d[n%2][G];
    return 0;
}