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

#define SIZE 5005

FILE *file;

typedef struct object{
    int use_rating;
    int weight;
} object;

int partial_points_matrix[5005][10005];

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

int main(void)
{
    object obj[SIZE];
    int n;
    int max_weight_bag;

    file = fopen("rucsac.in", "r");
    if(file == NULL)
    {
        exit(EXIT_FAILURE);
    }

    fscanf(file, "%d %d", &n, &max_weight_bag);

    for(int i = 0; i < n; ++ i)
    {
        fscanf(file, "%d %d", &obj[i].weight, &obj[i].use_rating);
    }

    fclose(file);




    for(int i = 1; i <= n; ++ i)//*in obj e de la 0
    {
        for(int w = 1; w <= max_weight_bag; ++ w)
        {   
            if(w - obj[i - 1].weight >= 0)                                                              /// *pt ca obj e de la 0
                partial_points_matrix[i][w] = max(partial_points_matrix[i - 1][w], partial_points_matrix[i - 1][w - obj[i - 1].weight] + obj[i - 1].use_rating);
            else
                partial_points_matrix[i][w] = partial_points_matrix[i - 1][w];
        }
    }
    

    file = fopen("rucsac.out", "w");

    fprintf(file, "%d\n", partial_points_matrix[n][max_weight_bag]);
    
    fclose(file);

    
    return 0;
}