#include<iostream>
#include<fstream>
using namespace std;
int n,G,x[10],maxim[10],pmax,nr;
struct obiect{
	int g,p;
};
	obiect a[10];
	
	void back(int i, int g, int p){
		int gnou,pnou;
		for(int j=x[i-1]+1; j<=n; j++)
		{
			x[i] = j;
			gnou = g + a[j].g;
			pnou = p+ a[j].p;
			if(gnou<=G)
			{
				if(pnou>pmax){
					pmax=pnou;
					nr = i;
					for(int k=1; k<=i; k++)
						maxim[k] = x[k];
				}
				back(i+1,gnou,pnou);
			}
		}
		
	}
int main(){
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	fin>>n>>G; 
	for(int i=1; i<=n; i++)
		fin>>a[i].g>>a[i].p;
	
	back(1,0,0);
	
	for(int j=1; j<=nr; j++)
		fout<<a[x[j]].p;
}