#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
int v[2][5005];
int main()
{
    int N,G;
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&N,&G);
    int x,y,k=0;
   for(register int i=1;i<=N;++i){
        scanf("%d%d",&x,&y);
        k=1-k;
        for(register int j=1;j<=G;++j){
            v[k][j]=v[1-k][j];
            if( v[ 1-k ][j - x ] + y > v[k][j] && x<=j   )      v[k][j]=v[ 1-k ][j - x ] + y;
        }
   }


    printf("%d",v[k][G]);
    return 0;
}