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

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

int knapsackDynamic(int N, int G, int weight[], int profit[]) {
    int *dp = (int *)malloc((G+1)*sizeof(int));
    if (dp==NULL) {
        printf("Error allocating memory\n");
        return 1;
    }
    memset(dp, 0, (G + 1)*sizeof(int)); //make all 0

    for (int i = 1; i<=N; i++) {
        for (int j= G; j>= weight[i-1]; j--) {
            dp[j] = max(dp[j], dp[j-weight[i-1]] + profit[i-1]);
        }
    }

    int result=dp[G];
    free(dp);
    return result;
}

int main() {
    FILE *fin=fopen("rucsac.in", "r");
    FILE *fout=fopen("rucsac.out", "w");

    if (fin == NULL || fout == NULL) {
        printf("Error opening the file\n");
        return 1;
    }
    int n, g;
    fscanf(fin, "%d %d", &n, &g);

    int *weight=(int *)malloc(n * sizeof(int));
    int *profit=(int *)malloc(n* sizeof(int));

    if (weight==NULL || profit==NULL) {
        printf("Error allocating memory\n");
        return 1;
    }

    for (int i=0; i<n; i++) {
        fscanf(fin, "%d %d", &weight[i], &profit[i]);
    }

    int solution=knapsackDynamic(n,g, weight, profit);
    fprintf(fout, "%d\n", solution);

    free(weight);
    free(profit);
    fclose(fin);
    fclose(fout);
    return 0;
}