#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("rucsac.in");
ofstream g ("rucsac.out");

int n, i, j, gmax, weight[5001], value[5001], greutate[5001], a[5001][5001];

void read ()
{
    f >> n >> gmax;
     for (i=1; i<=n; i++)
         f >> weight[i] >> value[i];
      for (i=1; i<=gmax; i++)
         greutate[i] = i;
}

int main()
{
   read();
      for (i=1; i<=n; i++)
           for (j=1; j<=gmax; j++)
           {
                  if (weight[i] <= j) {
                      a[i][j] = max( (a[i-1][j-weight[i]] + value[i] ), a[i-1][j]);
                  }
                       else {
                           a[i][j] = a[i-1][j];
                       }
           }
     g << a[n][gmax];
    return 0;
}