#include <cstdio>
#define nMax 5120
#define wMax 10240

using namespace std;

struct elem {
    int weight,value;
}v[nMax];

int n,w,sol[nMax][wMax];

void read() {
    int i;
    scanf("%d%d",&n,&w);
    for(i=0;i<n;++i)  {
        scanf("%d%d",&v[i].weight,&v[i].value);
    }
}

void solve() {
    int i,j;
    for(i=0;i<n;++i) {
        for(j=0;j<=w;++j) {
            if(i) {
                if(j>=v[i].weight&&sol[i-1][j-v[i].weight]+v[i].value>sol[i-1][j]) {
                    sol[i][j]=sol[i-1][j-v[i].weight]+v[i].value;
                }
                else {
                    sol[i][j]=sol[i-1][j];
                }
            }
            else {
                if(j>=v[i].weight) {
                    sol[i][j]=v[i].value;
                }
                else {
                    sol[i][j]=0;
                }
            }
        }
    }
}

int main() {
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    read();
    solve();
    printf("%d",sol[n-1][w]);
    return 0;
}