#include<fstream>
#include<iostream>
#define nmax 5001
#define maxg 10001
using namespace std;
int n,gmax;
int c[nmax],g[nmax];
int cmax[maxg], uz[maxg][nmax];
void citire();
void rezolvare();
void afisare();
int main()
{
	citire();
	rezolvare();
	afisare();
	return 0;
}
void citire()
{
	ifstream fin("rucsac.in");
	int i,j;
	fin>>n>>gmax;
	for(i=1;i<=n;i++)
	{	fin>>g[i];
		fin>>c[i];
	}
	fin.close();
}
void rezolvare()
{
	int s,k,i;
	for(s=1;s<=gmax;s++)
		cmax[s]=-1;
	for(s=1;s<=gmax;s++)
		for(i=1;i<=n;i++)
			if(g[i]<=s && cmax[s-g[i]]!=-1 && !uz[s-g[i]][i])
				if(cmax[s]<c[i]+cmax[s-g[i]])
				{
					cmax[s]=c[i]+cmax[s-g[i]];
					for(k=1;k<=n;k++)
						uz[s][k]=uz[s-g[i]][k];
					uz[s][i]=1;
				}
}
void afisare()
{
	ofstream fout("rucsac.out");
	fout<<cmax[gmax]<<endl;
	cout<<cmax[gmax]<<endl;
	fout.close();
}