#include <cstdio>
using namespace std;

int v[10005];

int main()
{

    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    int n, g, i, j, ma;
    int w, c;

    ma = -(1<<23);

    scanf("%d%d",&n,&g);
    for( i = 1; i <= n; ++i ){
        scanf("%d%d",&w,&c);
        for( j = g - w; j >= 0; --j ){
            if( v[j+w] < v[j] + c ){
              v[j+w] = v[j] + c;
              if( v[j+w] > ma ) ma = v[j+w];
            }

        }
    }

    printf("%d",ma);


    return 0;
}