#include <cstdio>
#define INF 100000000

using namespace std;

int w[5000], p[5000], d[5000][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[i - 1][j] > d[i - 1][j - w[i]] + p[i])
                {
                    d[i][j] = d[i - 1][j];
                }
                else
                {
                    d[i][j] = d[i - 1][j - w[i]] + p[i];
                }
            }
            else
            {
                d[i][j] = d[i - 1][j];
            }
        }
    }
    
    for(int i = 0; i <= g; i++){
        max = (max < d[n][i]) ? d[n][i] : max;
    }
    
    fprintf(out, "%d", max);
}