#include <iostream>
#include <iomanip>
#include <fstream>

//#define DEBUG true

#define NRO 5005
#define GRMAX 10005
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int w[NRO],p[NRO],G, n, a[NRO][GRMAX];

int main(){
	fin >> n >> G;
	for(int i=1;i<= n;i++)
		fin >> w[i] >> p[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=G;j++)
		{
			a[i][j] = a[i-1][j]; // nu punem obiectul i in rucsac
			if(w[i]<=j) // obiectul i incape in rucsac
				if(a[i][j] < a[i-1][j-w[i]] + p[i])
					a[i][j] = a[i-1][j-w[i]] + p[i];
		}
	#ifdef DEBUG
	for(int i = 0 ; i <= n ; ++i)
	{
		for (int j = 0 ; j <= G ; ++j)
			cout << setw(3) << a[i][j];
		cout << endl;
	}
	int  i = n , j = G;
	while(i>0)
	{
		if(a[i][j] == a[i-1][j])
			i -- ;
		else
		{
			cout << i << " ";
			j = j - w[i];
			i --;
		}
	}
	#endif
	fout <<a[n][G];
	

return 0;
}