#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=1; j<=gmax; j++)
       {
          if (j>=gr[i])
            a[i][j]=max(a[i-1][j-gr[i]]+co[i], a[i-1][j]);
          else a[i][j]=a[i-1][j];
       }
    }

    fout<<a[n][gmax];
    fin.close();
    fout.close();
    return 0;
}