#include <stdio.h>
int n, m;
int cst[15001], gr[15001],sol[5001],v[10001][10001],j;
void citire()
{
	
	FILE *f;
	f = fopen("in.txt", "rt");
	fscanf(f, "%d", &n);
	fscanf(f, "%d", &m);
	for (int i = 0; i < n; i++)
	{

		fscanf(f, "%d", &gr[i]);//citire fisier greutate
		fscanf(f, "%d", &cst[i]);//citire cost
		
	}
}
void init(int v[][1001])
{

	for (int i = 0; i < 100; i++)
		for (int x = 0; x < 100; x++)
			v[i][x] = -1;//initilizare cu -1;
}
int  incarcare(int k,int *j)
{
	for (int i = 0; i < k; i++)
		v[*j][i] = sol[i];
	//solutile se incarca in matrice
}
int ok(int k)
{
	int i,s=0,c=0;
	for (i = 0; i < k; i++)
	{
		s += gr[sol[i]];
		if ((s + gr[sol[k]]) > m || sol[i]>=sol[k])//daca suma greutatilor precedente + cea curenta depaseste m nu e solutie ok
			return 0;
	}
	return 1;
}
int max(int a,int b)
{
	if (a > b)
		return a;
	else
		return b;
}

void back(int k,int x)
{
	int i;
	if (k == x)
	{
		incarcare(k, &j); //la fiecare pas k incarcam in matrice
		j++;
	}
		else
			for (i = 0; i < n; i++)
			{
				sol[k] = i;//generam solutiile
				if (ok(k) == 1)//daca e solutie ok trecem la urmatorul pas
					back(k + 1,x);
			}
}
void rezolvare()
{
	FILE *f;
	f = fopen("rucsac.out", "wt");
	int maxi = 0, s;//suma cost
	int sgr = 0;//suma greutatre
	for (int i = 0; i < j; i++)
	{
		s = 0;
		for (int l = 0; l < n; l++)
		{
			if (v[i][l] >= 0)
				s += cst[v[i][l]];
			maxi = max(maxi, s);//gasim costul maxim in matrice
		}
	}
	for (int i = 0; i < j; i++)
	{
		s = 0;
		for (int l = 0; l < n; l++)
		{
			if (v[i][l] >= 0)
				s += cst[v[i][l]];
			if (s == maxi)//am gasit linia solutia cu cost maxim
			{
				int sgr = 0;
				for (int p = 0; p < n; p++)
				{

					if (v[i][p] >= 0)
						sgr += gr[v[i][p]];//calculeaza suma greutatilor
				}
				fprintf(f,"%d", maxi);
				//printf("");
				///for (int p = 0; p < n; p++)//mai parcurgem linia solutilor si afisam coeficientii
				//	if (v[i][p] >= 0)
						//fprintf(f,"%d ", v[i][p]);
				//fprintf(f,"\n");
				break;//oprim fortat dupa afisare
			}
		}
	}
}
int main()
{
	
	init(v);
	citire();
	for (int x = 1; x <= n; x++)
		back(0, x);
	rezolvare();
	system("pause");
}