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

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

int main(int argc, char const *argv[])
{
	FILE *read = fopen("rucsac.in", "r");
	FILE *write = fopen("rucsac.out", "w");

	int number_of_objects;
	int knapsack_capacity;

	fscanf(read, "%d%d", &number_of_objects, &knapsack_capacity);

	int *profits = (int*) calloc(number_of_objects + 1, sizeof(int));
	int *weights = (int*) calloc(number_of_objects + 1, sizeof(int));
	int ** partial_profits = (int**) calloc(2, sizeof(int*));

	for (int i = 0; i <= number_of_objects; i++)
	{
		if (i < number_of_objects)
			fscanf(read, "%d%d", &weights[i], &profits[i]);
		
		if(i == 0 || i == 1)
			partial_profits[i] = (int*) calloc(knapsack_capacity + 1, sizeof(int));
	}

	for (int i = 1 ; i <= number_of_objects; i++)
	{	
		for (int j = 1; j <= knapsack_capacity; j++)
		{
			if (weights[i-1] <= j)
				partial_profits[1][j] = max(partial_profits[0][j - weights[i-1]] + profits[i-1], partial_profits[0][j]);
			else
				partial_profits[1][j] = partial_profits[0][j];	
		}

		for(int j = 1; j <= knapsack_capacity; j++)
			partial_profits[0][j] = partial_profits[1][j];

	}
	fprintf(write, "%d\n", partial_profits[0][knapsack_capacity]);

	for (int i = 0; i <= 1; i++)
		free(partial_profits[i]);

	free(partial_profits);

	free(profits);
	free(weights);

	fclose(read);
	fclose(write);
	
	return 0;
}