#include <stdio.h>

int W[10001], P[10001];
int dp[5001];


int max(int a, int b){
    if(a > b) return a;
    return b;
}

int main(){

    FILE* f = fopen("rucsac.in", "rb");
    if(f == NULL){
        printf("Eroare la deschoderea fisierului");
        return 1;
    }

    int N, G;
    fscanf(f, "%d %d", &N, &G);

    for(int i = 0; i < N; i++)
        fscanf(f, "%d%d", &W[i], &P[i]);
    
    // W - greutatea
    // P - profitul

    // dp[i] = profitul maxim ai greutatea sa fie i
    // dp[j] = max(P[i-1] + dp[j - W[i-1]], dp[j]);

    int j = G;
    dp[0] = 0;
    for(int i = 1; i <=N; i++) // i = indicele ob
        for(int j = G; j >= 0 && j-W[i-1] >= 0; j--) // j - indicele greutatii
            dp[j] = max(P[i-1] + dp[j - W[i-1]], dp[j]);

    FILE* fout = fopen("rucsac.out", "wb");
    if(f == NULL){
        printf("Eroare la scrierea in fisier");
        return 1;
    }
    fprintf(fout, "%d", dp[G]);
    fclose(f);
}