#include <fstream>
using namespace std;
int d[5001][10001], masa[5001], val[5001];
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][g]=max(d[i-1][g-masa[i]]+val[i], d[i-1][g]);
        else
          d[i][g]=d[i-1][g];
    }
    for(int i=1; i<=G; i++)
      if(maxg<d[n][i])
        maxg=d[n][i];
    fout<<d[n][G];
    return 0;
}