#include <fstream>

using namespace std;

int N,G;
int greut[5001], values[5001], v[10001];


void get_data(){

ifstream in("rucsac.in");
in>>N>>G;

for(int i = 1; i <= N; i++)

    in >> greut[i] >> values[i];

in.close();

}

int main(){

get_data();

v[0] = 0;
for (int i = 1; i<=G; i++)
    v[i] = -1;


int rez = 0;

for (int i = 1; i <= N; i++)

  for (int j = G-greut[i]; j >= 0; j--)
  {

      int aux = v[ j + greut[i] ] ;
      int aux2 = v[j] + values[i];

      if (aux2 > aux && v[j] != -1) v[ j+ greut[i]] = aux2;

  }

for (int i = 0; i <= G; i++)
    if (v[i] > rez) rez = v[i];

ofstream out("rucsac.out");
out<<rez<<" ";
out.close();

return 0;

}