#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct elem
{
	int w, p;
};

bool cmp(elem i, elem j)
{
	if(i.p/i.w*1.0<j.p/j.w*1.0)
		return 1;
	else if(i.p/i.w*1.0>j.p/j.w*1.0)
		return 0;
	else
		return i.w<j.w;
}

int main()
{
    int n, g, i, pmax=0, ok, nrinr=0;
    elem v[5001], r[5001];
    in>>n>>g;
    for(int i=1; i<=n; i++)
	{
		in>>v[i].w>>v[i].p;
	}
	sort(v+1, v+n+1, cmp);
	for(int i=n; i>0; i--)
		cout<<i<<" "<<v[i].w<<" "<<v[i].p<<endl;
	i=n;
	while(g>0 and i>0)
	{
		cout<<i<<"_ ";
		if(v[i].w<=g){
			pmax+=v[i].p;
			g-=v[i].w;
			r[++nrinr]=v[i];
			cout<<v[i].p<<" ";
		}
		else
		{
			ok=1;
			for(int j=nrinr; j>0 and ok==1; j--)
			{
				if(v[i].p>=r[j].p and v[i].w<=g+r[j].w)
				{
					ok=0;
					g-=v[i].w-r[j].w;
					cout<<"-"<<j<<"  "<<v[i].p<<" ";
					pmax+=v[i].p-r[j].p;
					r[j]=v[i];
				}
			}
		}
		i--;
	}
	out<<pmax;
    return 0;
}