#include <cstdio>

using namespace std;
int w[5001], p[5001], opt[10001], n, g, i, j, sol;
int main()
{

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

    scanf("%d%d", &n, &g);

    //printf("%d  %d \n", n, g);
    for(i=1; i<=n; i++)
        scanf("%d %d", w+i, p+i);
   // for(i=1; i<=n; i++)
    //printf("%d ", w[i]);

    opt[0]=1;
    for(i=1; i<=n; i++){
        for(j=g-w[i]; j>=0; j--){
            if(opt[j] and opt[j+w[i]]<opt[j]+p[i]){
                opt[j+w[i]]=opt[j]+p[i];
                if(sol<opt[j+w[i]])
                    sol=opt[j+w[i]];
            }
        }
    }
    //for(i=0; i<=g; i++)   printf("%d ", opt[i]);
    printf("%d", sol-1);

    return 0;
}