#include <stdio.h>
#include <stdlib.h>

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

int knapsack(int N, int G, int weights[], int profits[]) {
    int *dp=NULL;
    dp=(int*)calloc(G+1,sizeof(int));


    for (int i = 0; i < N; i++) {
        for (int j = G; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + profits[i]);
        }
    }
    int x=dp[G];
    free(dp);
    return x;
}

int main() {
    int N, G;


    FILE *f=NULL;
    f=fopen("rucsac.in","r");
    if(f==NULL)exit(EXIT_FAILURE);
    
    fscanf(f,"%d", &N);
    fscanf(f,"%d", &G);

    int *weights=NULL;
    weights=(int*)calloc(G,sizeof(int));
    int *profits=NULL;
    profits=(int*)calloc(G,sizeof(int));


    for (int i = 0; i < N; i++) {
        fscanf(f,"%d", &weights[i]);
        fscanf(f,"%d", &profits[i]);
    }
    fclose(f);
    f=fopen("rucsac.out","w");
    if(f==NULL)exit(EXIT_FAILURE);
    // Calculate and display the result
    int maxProfit = knapsack(N, G, weights, profits);
    fprintf(f,"%d", maxProfit);
    fclose(f);
    free(weights);
    free(profits);


    return 0;
}