#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N , G,gr[5010],P[5010],i,cw,D[2][10010];
int main()
{
    f >> N >> G;
      for ( i = 1 ; i <= N ; i ++ )
        f >> gr[i] >> P[i] ;
    int l = 0;
    for ( i = 1 ; i <= N ; i ++, l = 1 - l)
     for ( cw = 0; cw <= G ; cw++ )
    {
        D[1-l][cw]=D[l][cw];

         if (gr[i] <= cw)
            D[1-l][cw] = max(D[1-l][cw], D[l][cw-gr[i]] + P[i]);
    }
    g << D[l][G];
    return 0;
}