#include<iostream>
#include<fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int gr[5005], co[5005], n, gmax, a[5005][10005];
int main ()
{
    int i, j;
    fin>>n>>gmax;
    for (i=1; i<=n; i++)
        fin>>gr[i]>>co[i];
    for (i=1; i<=n; i++)
    {
       for (j=gr[i]; j<=gmax; j++)
       {
          if (i==1)
          {
              if (j<gr[i])
                a[i][j]=0;
              else a[i][j]=co[i];
          }
          else a[i][j]=max(a[i-1][j-gr[i]]+co[i], a[i-1][j]);
       }
    }
    fout<<a[n][gmax];
    fin.close();
    fout.close();
    return 0;
}