#include <cstdio>
#define INF 100000000

using namespace std;

int w[5000], p[5000], d[2][10000], n, g;

int main(){
    FILE *in = fopen("rucsac.in", "r"), *out = fopen("rucsac.out", "w");
    int max = 0, t, u;

    fscanf(in, "%d%d", &n, &g);
    for(int i = 1; i <= n; i++){
        fscanf(in, "%d%d", &w[i], &p[i]);
    }

    for(int j = 0; j <= g; j++){
        d[1][j] = -1 * INF;
    }
    d[1][0] = 0;
    d[1][w[1]] = p[1];

    for(int i = 2; i <= n; i++){
        for(int j = 0; j <= g; j++){
            if(j >= w[i])
            {
                if(d[0][j] > d[0][j - w[i]] + p[i])
                {
                    d[1][j] = d[0][j];
                }
                else
                {
                    d[1][j] = d[0][j - w[i]] + p[i];
                }
            }
            else
            {
                d[1][j] = d[0][j];
            }
        }
        for(int j = 0; j <= g; j++){
            d[0][j] = d[1][j];
            d[1][j] = -1 * INF;
        }
    }

    for(int i = 0; i <= g; i++){
        max = (max < d[0][i]) ? d[0][i] : max;
    }

    fprintf(out, "%d", max);
}