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



typedef struct rucsac
{
	int capacitate;
	int pret;
	bool ok;
};


int max(int a, int b)
{
	if (a < b)
		return b;
	else
		return a;
}
int pret_max(int capacitate_max, rucsac* produse, int n)
{
	if (n == -1)
		return 0;
	int a;
	if (capacitate_max - produse[n].capacitate >= 0)
		a = pret_max(capacitate_max - produse[n].capacitate, produse, n - 1) + produse[n].pret;
	else
		a = 0;
	int b = pret_max(capacitate_max, produse, n - 1);
	return max(a, b);
}

int elemente(rucsac* produse, int n,int cost_max)
{
	int** c = (int**)malloc((cost_max + 1) * sizeof(int*));
	for (int i = 0; i <= cost_max; i++)
		c[i] = (int*)calloc((n + 1) ,sizeof(int));

	for (int i = 1; i <= cost_max; i++)
	{
		if (i < produse[0].capacitate)
			c[i][1] = 0;
		else
			c[i][1] = produse[0].pret;
	}


	for (int j = 2; j <= n; j++)
	{
		for (int i = 1; i <= cost_max; i++)
		{
			int max1 = c[i][j - 1];
			int max2 = 0;
			if (i >= produse[j - 1].capacitate)
				max2 = c[i - produse[j - 1].capacitate][j - 1] + produse[j - 1].pret;
			if (max1 > max2)
				c[i][j] = max1;
			else
				c[i][j] = max2;
		}
	}
	for(int i=1;i<=cost_max;i++,printf("\n"))
		for (int j = 1; j <= n; j++)
		{
			printf("%d ", c[i][j]);
		}
	return c[cost_max][n];
}
int main()
{
	int n,capacitate_max;
	FILE* fin = fopen("rucsac.in", "r");
	fscanf(fin, "%d%d", &n,&capacitate_max);
	rucsac* produse = (rucsac*)malloc(n * sizeof(rucsac));

	for (int i = 0; i < n; i++)
	{
		fscanf(fin, "%d%d", &produse[i].capacitate, &produse[i].pret);
		produse[i].ok = 0;
	}

	FILE* fout = fopen("rucsac.out", "w");
	


	fprintf(fout,"%d", elemente(produse, n, capacitate_max));
}