#include <cstdio>

using namespace std;

struct bine{
    int weight, profit;
}v[5001];

int d[3][10001];
int maxim(int a, int b){
    if(a > b)
        return a;
    return b;
}
int main()
{
    int i, j, pp, n, w, maxm = -1*0x3f3f3f3f;
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d%d", &n, &w);
    for(i=1; i<=n; ++i)
        scanf("%d%d", &v[i].weight, &v[i].profit);
    for(i=1; i<=n; ++i){
        for(j=0; j<=w; ++j)
        {
            d[2][j]=d[1][j];
            if(j>=v[i].weight)
                d[2][j] = maxim(d[2][j], d[1][j-v[i].weight]+v[i].profit);
        }
        for(j=0; j<=w; ++j)//{
            d[1][j]=d[2][j];
          //  printf("%d  ", d[1][j]);
        //}
        //printf("\n");
    }
    pp=1;
    for(i=w; i>=0; i--)
    {
        if(d[1][i] > maxm)
            maxm = d[1][i];
    }

    printf("%d\n", maxm);
    return 0;
}