#include <cstdio>
#define INF 50
#define MAX(i, j) (i < j) ? j : i

using namespace std;

int w[5000], p[5000], n, g;

int d(int i, int j){
    if(i == 1){
        if(j == 0){
            return 0;
        }
        else if(j == w[1]){
            return p[1];
        }
        else{
            return -1 * INF;
        }
    }
    else{
        int a = d(i - 1, j), b = (j >= w[i]) ? (d(i - 1, j - w[i]) + p[i]) : 0;
        return (a > b) ? a : b                               ;
    }
}

int main(){
    FILE *in = fopen("rucsac.in", "r"), *out = fopen("rucsac.out", "w");
    int max = 0, t;
    
    fscanf(in, "%d%d", &n, &g);
    for(int i = 1; i <= n; i++){
        fscanf(in, "%d%d", &w[i], &p[i]);
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= g; j++){
            fprintf(out, "%d\t", d(i,j));
        }
        fprintf(out, "\n");
    }
    
    for(int i = 0; i <= g; i++){
        t = d(n, i);
        max = (max < t) ? t : max;
    }
    
    fprintf(out, "%d", max);
}