#include<cstdio>
#define MAX_N 5000
#define MAX_W 10000
using namespace std;

struct elem {
    int weight, val;
};

elem v[MAX_N];
int dp[2][MAX_W+1], n, G, lc, lp;

inline int maxim(int a, int b) {
    if(a >= b) return a;
    return b;
}

int main() {
    int i, j;
    FILE* fin, *fout;
    fin = fopen("rucsac.in","r");
    fout = fopen("rucsac.out","w");
    fscanf(fin,"%d%d",&n,&G);
    for(i = 0; i < n; i++)
        fscanf(fin,"%d%d",&v[i].weight,&v[i].val);
    fclose(fin);
    lc = 1;
    lp = 0;
    for(i = 0; i < n; i++) {
        for(j = 0; j <= G; j++)
            if(j < v[i].weight)
                dp[lc][j] = dp[lp][j];
            else dp[lc][j] = maxim(dp[lp][j],dp[lp][j-v[i].weight]+v[i].val);
        lc = 1-lc;
        lp = 1-lp;
    }
    fprintf(fout,"%d\n",dp[lp][G]);
    fclose(fout);
    return 0;
}