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

typedef unsigned int uint;

#define MAX(a, b) ((a < b) ? b : a)

uint knapsack01(uint n, uint kg, uint *weights, uint *values);
uint **get_empty(uint n, uint m);

int main(void)
{
	FILE *in =  fopen("energii.in", "r");
	FILE *out = fopen("energii.out", "w");

	if(in != NULL && out != NULL)
	{
		uint weights[5100], values[5100], kg, n, i = 0;
		fscanf(in, "%u%*c%u%*c", &n, &kg);
		for(; i < n; i++)
		{
			uint a, b;
			fscanf(in, "%u%*c%u%*c", &a, &b);
			weights[i] = a;
			values[i] = b;
		}
		fprintf(out, "%u\n", knapsack01(n, kg, weights, values));

		fclose(in);
		fclose(out);
	}
	else
	{
		printf("file error\n");
	}

	return 0;
}

uint **get_empty(uint n, uint m)
{
	uint **matrix = malloc(sizeof(uint) * n);
	if(matrix != NULL)
	{
		uint i = 0;
		for(; i < n; i++)
		{
			uint *data = malloc(sizeof(uint) * m);
			if(data != NULL)
			{
				matrix[i] = data;
			}
		}
		return matrix;
	}
	else
	{
		printf("erro\n");
	}
}

uint knapsack01(uint n, uint kg, uint *weights, uint *values)
{
	uint **dp = get_empty(n + 1, kg + 1);
	uint i = 0;
	for(; i <= n; i++)
	{
		dp[i][0] = 0;
	}
	i = 0;
	for(; i <= kg; i++)
	{
		dp[0][i] = 0;
	}

	i = 1;
	for(; i <= n; i++)
	{
		uint j = 1;
		for(; j <= kg; j++)
		{
			if(weights[i - 1] <= j)
			{
				dp[i][j] = MAX(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	return dp[n][kg];
}